2010年02月11日星期四.sgu155 && pku2201
笛卡尔树的构造。
将所有节点按照k的大小从小到大排序，这样就得到了整棵树的中序遍历结果。
接下来，由于a符合堆的性质，我们只要递归的寻找区间中最大的a，就能构造出整棵树了。寻找
区间最大值，也就是rmq问题，用sparse table或者线段树都可以解决，这样整个算法就完成了。
sparse table 不会的，看这里,传送门:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Sparse_Table_%28ST%29_algorithm
上面有详细的 rmq,lca问题的算法
笛卡尔树在排好序的情况下有O(n)的构造方法，不过我不会...
不过要排序，最好的复杂度都是O(nlogn),时间差不了多少....
1
2 const int N = 50010;
3 int table[24][N],pow2[24];
4 int out[N][3];
5 struct L {
6 int a,k,idx;
7 int left,right,parent;
8 L(){}
9 }data[N];
10 bool cmp(const L& v1,const L& v2) { return v1.k < v2.k; }
11 int n,deep;
12
13 int rmq(int i,int j)
14 {
15 if (j < i) { swap(i,j); }
16 int two = floor(log2(j - i + 1));
17 int idx1 = table[two][i];
18 int idx2 = table[two][j-pow2[two] + 1];
19 if (data[idx1].a < data[idx2].a) {
20 return idx1;
21 }
22 return idx2;
23 }//http://www.cppblog.com/schindlerlee
24 void build_table()
25 {
26 int i,j,k;
27 sort(data,data + n,cmp);
28 for (i = 0;i <= 20;i++) { pow2[i] = 1 << i; }
29 for (i = 0;i < n;i++) {
30 table[0][i] = i;
31 }
32 deep = floor(log2(n));
33 for (i = 1;i <= deep;i++) {
34 for (j = 0;j + pow2[i-1] < n;j++) {
35 if (data[table[i-1][j]].a > data[table[i-1][j+pow2[i-1]]].a) {
36 table[i][j] = table[i-1][j+pow2[i-1]];
37 }else {
38 table[i][j] = table[i-1][j];
39
40 }
41 }
42 }
43 }
44
45 void dfs(int u,int beg,int end)
46 {
47 if (end <= beg) { return; }
48
49 int ux = data[u].idx;
50 if (u-1 >= beg) {
51 int l = rmq(beg,u - 1);
52 int lx = data[l].idx;
53 out[ux][1] = lx;
54 out[lx][0] = ux;
55 dfs(l,beg,u-1);
56 }
57 if (end >= u+1) {
58 int r = rmq(u + 1,end);
59 int rx = data[r].idx;
60 out[ux][2] = rx;
61 out[rx][0] = ux;
62 dfs(r,u+1,end);
63
64 }
65 }
66
67 int main()
68 {
69 int i,j,k;
70 scanf("%d",&n);
71 for (i = 0;i < n;i++) {
72 scanf("%d%d",&data[i].k,&data[i].a);
73 data[i].idx = i + 1;
74 }
75 puts("YES");
76 build_table();//构造rmq用的sparse table
77 dfs(rmq(0,n-1),0,n-1); //递归构造树
78 for (i = 1;i <= n;i++) {
79 printf("%d %d %d\n",out[i][0],out[i][1],out[i][2]);
80 }
81
82 return 0;
83 }
84