被这题虐了快两天。。。。。。。。。。。。

　　找最大的异或值显然用trie。。因为还要支持插入删除修改。。所以就用平衡树套trie。

　　如果旋转的话，整颗trie都要重新建，所以正常姿势是替罪羊树（虽然只是早建晚建的区别= =）

　　看了学长的解题报告后才敢用treap= =。。结果就陷入了无尽的调试中TAT..代码能力还是拙计...前前后后改了两天，大概得有8h+吧。。。

 

　　具体做法：每个treap的节点上建一颗高度为20的trie（因为数的大小<2^20），在trie中插入treap节点所在子树中的所有数字。

　　显然trie里面得动态开节点，而且还要垃圾回收。旋转的时候暴力重构trie就好了（注意常数）

　　垃圾回收千万别调stl的队列TAT。。。会慢一半以上。。自己写个栈就一行。。为何要去亲身感受stl的常数TAT

　　查询的时候就把在treap里拆成一个个对应的小区间和节点，用数组存着，顺便求出第二大的数值。计算异或值的时候可以一个一个跑，也可以一次在一颗trie上跑完。后一种的话要记得把已经无法匹配的节点丢掉，并且速度也比前一种快一些。。

　　感觉自己的常数已经没法再压了。。然而跑了倒数第2。。orz

　　运行了下云神的代码发现自己的删除操作慢了一倍多= =。。。至今原因不明TAT。。而且数据很多都是删除、插入的操作（针对替罪羊树）TAT。。其他操作还不慢。

　　一开始建treap的时候记得递归建树（最主要的是避免无谓的旋转）。。

代码长度还好。。不到6k。。我是应该高兴还是悲伤呢。。。

话说原来代码可读性这种东西真的是毫无下限的啊。。。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #define get top?st[top--]:++tt 8 using namespace std; 9 const int maxn=100033<<1; 10 const int maxm=maxn*160; 11 int two[21],len; 12 int ch[2][maxm],sm[maxm],tt;int st[maxm],top; 13 int l[maxn],r[maxn],num[maxn],sz[maxn],mx1[maxn],mx2[maxn],rnd[maxn],rt[maxn],tot,nowmx1,nowmx2; 14 int i,j,n,m,x,y,root,ans,tmp,V; 15 int ra;char rx; 16 inline int read(){ 17 rx=getchar(),ra=0; 18 while(rx<'0'||rx>'9')rx=getchar(); 19 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra; 20 } 21 inline void ins(int &rt,int v){ 22 if(!rt)rt=get;int x=rt;++sm[x]; 23 for(register int i=19;i>=0;i--) 24 if(v&two[i])++sm[ ch[1][x] ? x=ch[1][x] : x=ch[1][x]=get ];else 25 ++sm[ ch[0][x]?x=ch[0][x]:x=ch[0][x]=get ]; 26 } 27 inline void clr(int &x){ 28 st[++top]=x,sm[x]=0; 29 if(ch[0][x])clr(ch[0][x]);if(ch[1][x])clr(ch[1][x]); 30 x=0; 31 } 32 inline void del(int x,int v){ 33 --sm[x];bool k; 34 for(register int i=19,j=x;i>=0;j=x,i--){ 35 if(v&two[i])x=ch[k=1][j];else x=ch[k=0][j]; 36 if(!(--sm[x])){ch[k][j]=0,clr(x);return;} 37 } 38 } 39 inline void update(int &x,int l,int r){ //merge 40 x=get,sm[x]=sm[l]+sm[r]; 41 if(ch[0][l]||ch[0][r])update(ch[0][x],ch[0][l],ch[0][r]); 42 if(ch[1][l]||ch[1][r])update(ch[1][x],ch[1][l],ch[1][r]); 43 } 44 45 inline void upd(int x,int l,int r){ 46 sz[x]=sz[l]+sz[r]+1; 47 if(mx1[l]
            
             >1)+tot,num[x]=mx1[x]=v,sz[x]=1,ins(rt[x],v);return;} 63 sz[x]++,ins(rt[x],v); 64 if(v>mx1[x])mx2[x]=mx1[x],mx1[x]=v;else if(v>mx2[x])mx2[x]=v; 65 if(po>sz[l[x]]+1){ 66 insert(r[x],po-sz[l[x]]-1,v); 67 if(rnd[r[x]]
             
              nowmx1)nowmx2=nowmx1,nowmx1=mx1[x];else if(mx1[x]>nowmx2)nowmx2=mx1[x]; 92 if(mx2[x]>nowmx2)nowmx2=mx2[x]; 93 return; 94 } 95 if(L>sz[l[x]]+1)getmx(r[x],L-sz[l[x]]-1,R-sz[l[x]]-1); 96 else if(R<=sz[l[x]])getmx(l[x],L,R); 97 else{ 98 if(num[x]>nowmx1)nowmx2=nowmx1,nowmx1=num[x];else if(num[x]>nowmx2)nowmx2=num[x]; 99 st2[++top2]=num[x];100 if(L<=sz[l[x]])getmx(l[x],L,sz[l[x]]);if(R>sz[l[x]]+1)getmx(r[x],1,R-sz[l[x]]-1);101 }102 }103 inline int query(int l,int r){104 nowmx1=nowmx2=top1=top2=0,getmx(root,l,r);105 register int i,j,tmp;int ans=0,now=0;bool k,flag;106 for(;top2;top2--)if((nowmx2^st2[top2])>ans)ans=nowmx2^st2[top2];107 for(i=19;i>=0&&top1&&(now+two[i+1]-1>ans);--i){108 for(k=!(nowmx2&two[i]),j=top1,flag=0;j;--j)if(ch[k][st1[j]]){flag=1;break;}109 for(j=1,tmp=top1,top1=0,now+=flag?two[i]:0,k^=!flag;j<=tmp;++j)if(ch[k][st1[j]])st1[++top1]=ch[k][st1[j]];110 }111 return now
              
               R)return;115 x=(L+R)>>1;tot++;116 if(L
               
                'Z';id=getchar());133 x=read()+ans;if(x>=sz[root])x%=sz[root];134 if(id!='D'){135 y=read()+ans;136 if(id!='F')if(y>=1048576)y%=1048576;else;137 else if(y>=sz[root])y%=sz[root];138 }139 x++;if(id=='F')y++;140 if(id=='I')insert(root,x,y);141 if(id=='D')delet(root,x);142 if(id=='C')change(root,x,y);143 if(id=='F'){ if(x>y)swap(x,y);ans=query(x,y),outx(ans);}144 }145 return 0;146 }