POJ 2201 Cartesian Tree
构造笛卡尔树。我用的是 排序+左旋 的方式，这种方式并不是最好的构造方式，先写出来再说，今天不行了，改天在学习其他的算法。
排序+左旋：
[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;
}
补充：软件开发 , C++ ,
