题意：
给出一些节点，每个节点有两个值，lable和priority，要求构成一个笛卡尔树，按lable是二叉排序树，按priority是大根堆（不一定完全二叉树）。输出括号表示。
思路：
没什么好说的，完全自己独立写的代码，除了读入参考了rainy days的，其他都是独立创造的~自我感觉写的还可以~
（抑郁，把括号表示法搞反了，纠结了好久，外面的括号越少的是堆顶！
又一直以为只有一个字母，又纠结了好久，可以是一个字符串！）
读入说明见：http://www.cnblogs.com/rainydays/archive/2011/06/15/2081266.html
PS：字符串s是二叉排序树结构，权值w是大根堆结构！
View Code
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 7 #define SIZE 101 8 #define N 50500 9 10 using namespace std; 11 12 struct PO 13 { 14 int w; 15 char s[SIZE]; 16 }po[N]; 17 18 struct TR 19 { 20 int u,l,r; 21 }tr[N*2]; 22 23 int n,lg[N],pn[N][20],cnt; 24 25 inline bool cmp(const PO &a,const PO &b) 26 { 27 return strcmp(a.s,b.s)<=0; 28 } 29 30 void read() 31 { 32 for(int i=1;i<=n;i++) 33 scanf("%*[ ]%[^/]/%d",po[i].s,&po[i].w); 34 sort(po+1,po+1+n,cmp); 35 } 36 37 inline int jmax(int x,int y) 38 { 39 if(po[x].w<po[y].w) return y; 40 else return x; 41 } 42 43 inline int askmax(int l,int r) 44 { 45 int k=lg[r-l+1]; 46 return jmax(pn[l][k],pn[r-(1<<k)+1][k]); 47 } 48 49 void init_rmq() 50 { 51 for(int i=1;i<=n;i++) pn[i][0]=i; 52 for(int j=1;(1<<j)<=n;j++) 53 for(int i=1;i+(1<<j)-1<=n;i++) 54 pn[i][j]=jmax(pn[i][j-1],pn[i+(1<<(j-1))][j-1]); 55 } 56 57 void create(int u,int l,int r) 58 { 59 if(r<l) return; 60 int pos=askmax(l,r); 61 tr[u].u=pos; 62 if(l<=pos-1) 63 { 64 tr[u].l=++cnt; 65 create(cnt,l,pos-1); 66 } 67 if(r>=pos+1) 68 { 69 tr[u].r=++cnt; 70 create(cnt,pos+1,r); 71 } 72 } 73 74 void dfs(int u) 75 { 76 if(u==-1) return; 77 printf("("); 78 dfs(tr[u].l); 79 printf("%s/%d",po[tr[u].u].s,po[tr[u].u].w); 80 dfs(tr[u].r); 81 printf(")"); 82 } 83 84 void go() 85 { 86 memset(tr,-1,sizeof tr); 87 cnt=1; 88 init_rmq(); 89 create(1,1,n); 90 dfs(1); 91 puts(""); 92 } 93 94 int main() 95 { 96 for(int i=1;i<N;i++) 97 lg[i]=(i>>lg[i-1]+1)?lg[i-1]+1:lg[i-1]; 98 while(scanf("%d",&n),n) 99 { 100 read(); 101 go(); 102 } 103 return 0; 104 }