ZOJ 3765 splay(二)
kind); } } } if(goal==0)root=x; } int Get_kth(int x,int k) { int sz=siz[ch[x][0]]+1; if(sz==k)return x; if(sz>k)return Get_kth(ch[x][0],k); return Get_kth(ch[x][1],k-sz); } void Modify(int x,int k){ Splay(Get_kth(root,x),0); key[root]=k; push_up(root); } void update(int x) { Splay(Get_kth(root,x),0); rev[root]^=1; push_up(root); } void Insert(int x,int k,int staus){ Splay(Get_kth(root,x),0); int t_root=ch[root][1]; newnode(ch[root][1],root,k,staus); ch[ch[root][1]][1]=t_root; pre[t_root]=ch[root][1]; push_up(ch[root][1]); push_up(root); } void Remove(int x){ Splay(Get_kth(root,x-1),0); Splay(Get_kth(root,x+1),root); ch[ch[root][1]][0]=0; push_up(ch[root][1]); push_up(root); } void built(int &x,int L,int R,int fa) { if(L>R)return; int mid=(R+L)>>1; newnode(x,fa,A[mid].num,A[mid].staus); built(ch[x][0],L,mid-1,x); built(ch[x][1],mid+1,R,x); push_up(x); } void init(int n) { siz[0]=gcd[0][0]=gcd[0][1]=0; key[root=0]=tot=ch[0][0]=ch[0][1]=0; for(int i=1;i<=n;i++){ scanf("%d%d",&A[i].num,&A[i].staus); } newnode(root,0,0,0); newnode(ch[root][1],root,0,0); built(ch[ch[root][1]][0],1,n,ch[root][1]); } int Query(int L,int R,int staus) { Splay(Get_kth(root,L-1),0); Splay(Get_kth(root,R+1),root); int x=ch[ch[root][1]][0]; return gcd[x][staus]; } int main(int argc, char const *argv[]) { int n,Q,L,R,staus; while(~scanf("%d%d",&n,&Q)){ init(n); char cmd[5]; while(Q--){ scanf("%s",cmd); if(cmd[0]=='Q'){ scanf("%d%d%d",&L,&R,&staus); int ans=Query(L+1,R+1,staus); if(!ans)ans=-1; printf("%d\n",ans); }else if(cmd[0]=='D'){ scanf("%d",&L); Remove(L+1); }else if(cmd[0]=='I'){ scanf("%d%d%d",&L,&R,&staus); Insert(L+1,R,staus); }else if(cmd[0]=='R'){ scanf("%d",&L); update(L+1); }else{ scanf("%d%d",&L,&R); Modify(L+1,R); } } } return 0; }