構造笛卡爾樹。 我用的是 排序+左旋 的方式，這種方式並不是最好的構造方式，先寫出來再說，今天不行了，改天在學習其他的算法。 排序+左旋： [cpp] #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct node { int key, value, idx, lson, rson, fa; } a[50005]; struct renode { int fa, lson, rson, idx; } b[50005]; int n; bool cmp_key(const node &x, const node &y) { return x.key < y.key; } bool cmp_value(const node &x, const node &y) { return x.value < y.value; } void Insert(int now) { int j = now - 1; while (a[j].value > a[now].value) j = a[j].fa; a[now].lson = a[j].rson; a[a[j].rson].fa = now; a[j].rson = now; a[now].fa = j; } int main() { while (scanf("%d", &n) == 1) { for (int i=1; i<=n; i++) { scanf("%d %d", &a[i].key, &a[i].value); a[i].lson = a[i].rson = a[i].fa = 0; a[i].idx = i; } bool flag = true; sort(a+1, a+1+n, cmp_value); for (int i=1; i<n; i++) if (a[i].value == a[i+1].value) { flag = false; break; } if (!flag) { printf("NO\n"); continue; } sort(a+1, a+1+n, cmp_key); for (int i=1; i<n; i++) if (a[i].key == a[i+1].key) { flag = false; break; } if (!flag) { printf("NO\n"); continue; } a[0].lson = a[0].rson = a[0].fa = 0; a[0].value = -0x3f7f7f7f; a[0].idx = 0; for (int i=1; i<=n; i++) Insert(i); printf("YES\n"); for (int i=1; i<=n; i++) { b[a[i].idx].fa = a[a[i].fa].idx; b[a[i].idx].lson = a[a[i].lson].idx; b[a[i].idx].rson = a[a[i].rson].idx; } for (int i=1; i<=n; i++) printf("%d %d %d\n", b[i].fa, b[i].lson, b[i].rson); } return 0; }
