2010年02月11日星期四.sgu155 && pku2201
笛卡爾樹的構(gòu)造。
將所有節(jié)點按照k的大小從小到大排序，這樣就得到了整棵樹的中序遍歷結(jié)果。
接下來，由于a符合堆的性質(zhì)，我們只要遞歸的尋找區(qū)間中最大的a，就能構(gòu)造出整棵樹了。尋找
區(qū)間最大值，也就是rmq問題，用sparse table或者線段樹都可以解決，這樣整個算法就完成了。
sparse table 不會的，看這里,傳送門:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Sparse_Table_%28ST%29_algorithm
上面有詳細(xì)的 rmq,lca問題的算法
笛卡爾樹在排好序的情況下有O(n)的構(gòu)造方法，不過我不會...
不過要排序，最好的復(fù)雜度都是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.shnenglu.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();//構(gòu)造rmq用的sparse table
77 dfs(rmq(0,n-1),0,n-1); //遞歸構(gòu)造樹
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