版权声明：本文为博主原创文章，未经博主允许不得转载。
Splay树是一种神奇的东西。。。
题意：
有一些箱子，要么放在地上，要么放在某个箱子里面 。
现在有两种操作：
（1） MOVE x y： 把 x 号箱子放到 y 号箱子里面，操作不合法就忽略这一次操作 。
（2） QUERY x : 查询 x 号箱子最外面的箱子是哪一个
解法：
首先对所有的树进行一遍DFS，得到一个DFS序，可以把它看成是一个括号序列，开始访问某个节点是左括号，结束访问时是右括号 。这样这题就转换成用Splay树来维护这个序列 。
对于MOVE操作：
将 x 对应那一段序列切下来，并将其放到 y 对应左括号的右边 。
对于QUERY操作：
直接查询以 x 为根的子树的最小值 。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #include <queue> 7 #include <set> 8 #include <vector> 9 #include <map> 10 #define ll long long 11 12 using namespace std; 13 14 const int N=50007; 15 16 // 前向星 17 struct edge{ 18 int to,nex; 19 }e[N]; 20 int cnt; 21 int head[N]; 22 23 inline void addedge(int u,int v){ 24 e[cnt].to=v; 25 e[cnt].nex=head[u]; 26 head[u]=cnt++; 27 } 28 29 int id[N*2]; // DFS序 30 int cou; 31 32 int tot; 33 struct tree{ 34 int key,fa,son[2]; 35 }t[N*2]; 36 int L[N],R[N]; // 第i个箱子所对应的左右括号在Splay树上的序号 37 38 inline void pushup(int x){} 39 inline void pushdown(int x){} 40 41 inline void rotate(int x,int p){ 42 int y=t[x].fa; 43 pushdown(y); 44 pushdown(x); 45 46 t[y].son[!p]=t[x].son[p]; 47 t[t[x].son[p]].fa=y; 48 t[x].fa=t[y].fa; 49 if (t[x].fa) 50 t[t[x].fa].son[t[t[x].fa].son[1]==y]=x; 51 t[x].son[p]=y; 52 t[y].fa=x; 53 pushup(y); 54 pushup(x); 55 } 56 57 inline void Splay(int x,int to){ 58 while (t[x].fa!=to){ 59 if (t[t[x].fa].fa==to) 60 rotate(x,t[t[x].fa].son[0]==x); 61 else { 62 int y=t[x].fa, z=t[y].fa; 63 int p=(t[z].son[0]==y); 64 if (t[y].son[p]==x) 65 rotate(x,!p),rotate(x,p); 66 else 67 rotate(y,p),rotate(x,p); 68 } 69 } 70 } 71 72 inline int newnode(int key,int fa){ 73 int x=tot++; 74 t[x].key=key; 75 t[x].fa=fa; 76 t[x].son[0]=t[x].son[1]=0; 77 78 if (key>0) L[key]=x; 79 else R[-key]=x; 80 81 return x; 82 } 83 84 inline int get_min(int x){ 85 while (t[x].son[0]!=0) 86 x=t[x].son[0]; 87 return x; 88 } 89 90 inline int get_max(int x){ 91 while (t[x].son[1]!=0) 92 x=t[x].son[1]; 93 return x; 94 } 95 96 inline int bulid(int l,int r,int fa){ 97 if (l>r) return 0; 98 int x,mid=(l+r)>>1; 99 x=newnode(id[mid],fa); 100 t[x].son[0]=bulid(l,mid-1,x); 101 t[x].son[1]=bulid(mid+1,r,x); 102 pushup(x); 103 return x; 104 } 105 106 inline void dfs(int u){ 107 id[cou++]=u; 108 for (int i=head[u];~i;i=e[i].nex) 109 dfs(e[i].to); 110 id[cou++]=-u; 111 } 112 113 inline void init(){ 114 memset(head,-1,sizeof(head)); 115 cnt=0; 116 cou=0; 117 tot=1; 118 } 119 120 inline int query(int a){ 121 int x=L[a]; 122 Splay(x,0); 123 x=get_min(x); 124 return t[x].key; 125 } 126 127 inline void move(int a,int b){ 128 if (a==b) return; 129 130 int x=L[a],y=R[a]; 131 Splay(x,0); 132 Splay(y,x); 133 134 int xx=t[x].son[0],yy=t[y].son[1],z=0; 135 z=get_max(xx); 136 137 t[x].son[0]=0; t[y].son[1]=0; 138 t[xx].fa=0; t[yy].fa=0; 139 if (z!=0) t[z].son[1]=yy; 140 t[yy].fa=z; 141 142 if (b==0) return; 143 144 if (query(b)==a){ 145 t[x].son[0]=xx; t[y].son[1]=yy; 146 t[xx].fa=x; t[yy].fa=y; 147 t[z].son[1]=0; 148 return; 149 } 150 151 int l=L[b],r; 152 Splay(l,0); 153 r=get_min(t[l].son[1]); 154 Splay(r,l); 155 t[r].son[0]=x; 156 t[x].fa=r; 157 } 158 159 int main(){ 160 int n,q; 161 int x,y; 162 char ch[10]; 163 bool f=false; 164 while (scanf("%d",&n)!=EOF){ 165 if (f) puts(""); 166 else f=true; 167 168 init(); 169 170 for (int i=1;i<=n;i++){ 171 scanf("%d",&x); 172 addedge(x,i); 173 } 174 175 dfs(0); 176 int k=0,st=1; 177 for (int i=1;i<=2*n;i++){ 178 if (id[i]>0) k++; 179 else k--; 180 if (k==0) { 181 bulid(st,i,0); 182 st=i+1; 183 } 184 } 185 186 scanf("%d",&q); 187 while (q--){ 188 scanf("%s",ch); 189 if (ch[0]=='Q') { 190 scanf("%d",&x); 191 printf("%d ",query(x)); 192 } 193 else { 194 scanf("%d %d",&x,&y); 195 move(x,y); 196 } 197 } 198 } 199 200 return 0; 201 }