1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 #include<stack> 11 using namespace std; 12 #define N 100010 13 #define LL long long 14 #define INF 0xfffffff 15 const double eps = 1e-8; 16 const double pi = acos(-1.0); 17 const double inf = ~0u>>2; 18 int n,po[N]; 19 vector<int>ed[N]; 20 vector<int>dd; 21  22 struct splay_tree 23 { 24     int pre[N]; 25     int ch[N][2]; 26     int root,tot,num; 27     int key[N]; 28 //    void dfs(int x) 29 //    { 30 //        if(x) 31 //        { 32 //            dfs(ch[x][0]); 33 //            printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d,key=%2d\n", 34 //                   x,ch[x][0],ch[x][1],pre[x],size[x],key[x]); 35 //            dfs(ch[x][1]); 36 //        } 37 //    } 38 //    void debug() 39 //    { 40 //        printf("root:%d\n",root); 41 //        dfs(root); 42 //    } 43 //以上用于debug*/ 44     void newnode(int &x,int v,int fa)//新建一结点 45     { 46         x = ++tot; 47         ch[x][0]=ch[x][1] = 0; 48         pre[x] = fa; 49         key[x] = v; 50         po[v] = x; 51     } 52     void pushup(int w)//由儿子更新其父亲 53     { 54     } 55     void rotate(int r,int kind)//旋转操作，根据kind进行左旋和右旋 56     { 57         int y = pre[r]; 58         ch[y][!kind] = ch[r][kind]; 59         pre[ch[r][kind]] = y; 60         if(pre[y]) 61         { 62             ch[pre[y]][ch[pre[y]][1]==y] = r; 63         } 64         pre[r] = pre[y]; 65         ch[r][kind] = y; 66         pre[y] = r; 67         pushup(y); 68         pushup(r); 69     } 70     void splay(int r,int goal)//将r结点旋至goal下 71     { 72         while(pre[r]!=goal) 73         { 74             if(pre[pre[r]]==goal) 75             { 76                 rotate(r,ch[pre[r]][0]==r); 77             } 78             else 79             { 80                 int y = pre[r]; 81                 int kind = (ch[pre[y]][0]==y); 82                 if(ch[y][kind]==r) 83                 { 84                     rotate(r,!kind); 85                     rotate(r,kind); 86                 } 87                 else 88                 { 89                     rotate(y,kind); 90                     rotate(r,kind); 91                 } 92             } 93         } 94         pushup(r); 95         if(goal==0) root = r; 96     } 97     int get_min(int x) 98     { 99         while(ch[x][0])100             x =  ch[x][0];101         return x;102     }103     int get_max(int x)104     {105         while(ch[x][1])106             x = ch[x][1];107         return x;108     }109     void update(int x,int y) //更新区间信息110     {111         int l = po[x],r = po[x+n];112         splay(l,0);113         splay(r,0);114         int ll = ch[l][0];115         int rr = ch[r][1];116         pre[ll] = pre[rr] = 0;117         ch[r][1] = ch[l][0] = 0;118 119         int tll = get_max(ll);120         if(tll!=0)121             ch[tll][1] = rr;122         pre[rr] = tll;123 124         if(y==0) return ;125         if(query(y)==x)126         {127             ch[r][1] = rr;128             ch[l][0] = ll;129             pre[ll] = l;130             pre[rr] = r;131             ch[tll][1] = 0;132             pre[0] = 0;133             return ;134         }135 136         if(rr!=0) splay(rr,0);137         int tt = po[y];138         splay(tt,0);139         int tq = get_min(ch[tt][1]);140         splay(tq,tt);141         ch[tq][0] = r;142         pre[r] = tq;143     }144     int query(int x)//询问l,r区间，将第l-1个结点旋自根，第r+1个结点旋自根的有儿子，145     {146         splay(po[x],0);147         int k = get_min(po[x]);148         return key[k];149     }150     void build(int &x,int l,int r,int fa)151     {152         int m = (l+r)>>1;153         if(l>r) return ;154         newnode(x,dd[m],fa);155         build(ch[x][0],l,m-1,x);156         build(ch[x][1],m+1,r,x);157         pushup(x);158     }159     void init()160     {161         root = tot = 0;162         memset(ch,0,sizeof(ch));163         memset(pre,0,sizeof(pre));164         memset(key,0,sizeof(key));165         memset(po,0,sizeof(po));166     }167 } SP;168 void dfs(int u)169 {170     int i;171     dd.push_back(u);172     for(i = 0; i  < ed[u].size(); i++)173     {174         int v = ed[u][i];175         dfs(v);176     }177     dd.push_back(u+n);178 }179 int main()180 {181     int i;182     int q;183     int mark = false;184     while(scanf("%d",&n)!=EOF)185     {186         if(mark)187             puts("");188         else189             mark = true;190         SP.init();191         for(i = 0; i <= n; i++)192         {193             ed[i].clear();194         }195         dd.clear();196         for(i = 1; i <= n; i++)197         {198             int x;199             scanf("%d",&x);200             ed[x].push_back(i);201         }202         dfs(0);203         int o = 1;204         scanf("%d",&q);205         stack<int>st;206         for(i = 1 ; i < dd.size()-1 ; i++)207         {208             int x = dd[i];209             if(x<=n) st.push(x);210             else st.pop();211             if(st.empty())212             {213                 SP.build(SP.root,o,i,0);214                 o = i+1;215             }216         }217         int stt = 1;218         while(q--)219         {220             char sq[100];221             int x,y;222             scanf("%s",sq);223             if(sq[0]==‘Q‘)224             {225                 scanf("%d",&x);226                 printf("%d\n",SP.query(x));227             }228             else229             {230                 scanf("%d%d",&x,&y);231                 SP.update(x,y);232             }233         }234     }235     return 0;236 }