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 using namespace std; 11 #define N 300010 12 #define LL long long 13 #define INF 0xfffffff 14 #define key_value ch[ch[root][1]][0] 15 const double eps = 1e-8; 16 const double pi = acos(-1.0); 17 const double inf = ~0u>>2; 18 using namespace std; 19 int a[N][2]; 20 struct splay_tree 21 { 22     int pre[N],size[N],vv[N]; 23     int ch[N][2]; 24     int root,n,tot,num,tot1; 25     int s[N][2],sta[N],key[N]; 26     void dfs(int x) 27     { 28         if(x) 29         { 30             dfs(ch[x][0]); 31             printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d,key=%2d s0=%d  s1 = %d vv=%d\n", 32                    x,ch[x][0],ch[x][1],pre[x],size[x],key[x],s[x][0],s[x][1],vv[x]); 33             dfs(ch[x][1]); 34         } 35     } 36     void debug() 37     { 38         printf("root:%d\n",root); 39         dfs(root); 40     } 41 //以上用于debug*/ 42     void newnode(int &x,int v,int sta,int fa)//新建一结点 43     { 44         x = ++tot; 45         ch[x][0]=ch[x][1] = 0; 46         pre[x] = fa; 47         s[x][0] = s[x][1] = 0; 48         s[x][sta] = v; 49         size[x] = 1; 50         vv[x] = sta; 51         key[x] = v; 52     } 53     void pushup(int w)//由儿子更新其父亲 54     { 55         size[w] = size[ch[w][0]]+size[ch[w][1]]+1; 56         int st = vv[w]; 57         int l = ch[w][0],r = ch[w][1]; 58         int cnt1 = 0,cnt2 = 0; 59         cnt1 = s[l][0]; 60         if(s[r][0]) 61         { 62             if(cnt1) cnt1 = __gcd(s[r][0],cnt1); 63             else cnt1 = s[r][0]; 64         } 65         cnt2 = s[l][1]; 66         if(s[r][1]) 67         { 68             if(cnt2) cnt2 = __gcd(s[r][1],cnt2); 69             else cnt2 = s[r][1]; 70         } 71         s[w][0] = cnt1,s[w][1] = cnt2; 72         s[w][st] = s[w][st]?__gcd(s[w][st],key[w]):key[w]; 73         //cout<<s[w][0]<<" "<<s[w][1]<<endl; 74     } 75     void rotate(int r,int kind)//旋转操作，根据kind进行左旋和右旋 76     { 77         int y = pre[r]; 78         ch[y][!kind] = ch[r][kind]; 79         pre[ch[r][kind]] = y; 80         if(pre[y]) 81         { 82             ch[pre[y]][ch[pre[y]][1]==y] = r; 83         } 84         pre[r] = pre[y]; 85         ch[r][kind] = y; 86         pre[y] = r; 87         pushup(y); 88         pushup(r); 89     } 90     void splay(int r,int goal)//将r结点旋至goal下 91     { 92         while(pre[r]!=goal) 93         { 94             if(pre[pre[r]]==goal) 95             { 96                 rotate(r,ch[pre[r]][0]==r); 97             } 98             else 99             {100                 int y = pre[r];101                 int kind = (ch[pre[y]][0]==y);102                 if(ch[y][kind]==r)103                 {104                     rotate(r,!kind);105                     rotate(r,kind);106                 }107                 else108                 {109                     rotate(y,kind);110                     rotate(r,kind);111                 }112             }113         }114         pushup(r);115         if(goal==0) root = r;116     }117     int get_k(int k)//得到第k个的结点118     {119         int r = root;120         while(size[ch[r][0]]+1!=k)121         {122             if(size[ch[r][0]]>=k)123                 r = ch[r][0];124             else125             {126                 k-=(size[ch[r][0]]+1);//根据左右结点的数量来确定第k个节点在哪里127                 r = ch[r][1];128             }129         }130         pushup(r);131         return r;132     }133     void add(int k,int val,int sta)//添加一个结点 位置自己修改 这里为第一个134     {135         splay(get_k(k),0);136         splay(get_k(k+1),root);137         int r = ch[root][1];138         newnode(ch[r][0],val,sta,r);139         pushup(r);140         pushup(root);141     }142     void updelete(int r)//删除第r个结点143     {144         splay(get_k(r),0);145         splay(get_k(r+2),root);146         key_value = http://www.mamicode.com/0;147         pushup(ch[root][1]);148         pushup(root);149     }150     void update(int k,int flag,int v) //更新区间信息151     {152         splay(get_k(k),0);153         splay(get_k(k+2),root);154         if(flag)155         {156             vv[key_value]^=1;157             swap(s[key_value][1],s[key_value][0]);158         }159         else160         {key[key_value] = v;s[key_value][vv[key_value]] = v;}161         pushup(ch[root][1]);162         pushup(root);163 164     }165     int query(int l,int r,int sta)//询问l,r区间，将第l-1个结点旋自根，第r+1个结点旋自根的有儿子，166     {167         //则l-r就变成了根的右儿子的左儿子168         splay(get_k(l),0);169         splay(get_k(r+2),root);170         return s[key_value][sta];171     }172     void build(int &x,int l,int r,int fa)173     {174         int m = (l+r)>>1;175         if(l>r) return ;176         newnode(x,a[m][0],a[m][1],fa);177         build(ch[x][0],l,m-1,x);178         build(ch[x][1],m+1,r,x);179         pushup(x);180     }181     void init(int o)182     {183         int i;184         for(i = 1; i <= o; i++)185         scanf("%d%d",&a[i][0],&a[i][1]);186         size[0] = ch[0][0] = ch[0][1] = s[0][0] = s[0][1] = key[0] = vv[0] = 0;187         root = tot = 0;188         newnode(root,0,0,0);189         newnode(ch[root][1],0,0,root);190         build(ch[ch[root][1]][0],1,o,ch[root][1]);191         size[root] = 2;192         pushup(ch[root][1]);193         pushup(root);194     }195 }SP;196 int main()197 {198     int n,q;199     while(scanf("%d%d",&n,&q)!=EOF)200     {201         SP.init(n);202         while(q--)203         {204             char sq[20];205             int k,x,y;206             scanf("%s%d",sq,&k);207             if(sq[0]==‘I‘)208             {209                 scanf("%d%d",&x,&y);210                 SP.add(k+1,x,y);211                // SP.debug();212             }213             else if(sq[0]==‘D‘)214             {215                 SP.updelete(k);216             }217             else if(sq[0]==‘R‘)218             {219                 SP.update(k,1,0);220             }221             else if(sq[0]==‘M‘)222             {223                 scanf("%d",&x);224                 SP.update(k,0,x);225             }226             else if(sq[0]==‘Q‘)227             {228                 scanf("%d%d",&x,&y);229                 int ans = SP.query(k,x,y);230                 if(ans==0)231                 printf("-1\n");232                 else233                 printf("%d\n",ans);234                // SP.debug();235             }236         }237     }238     return 0;239 }