题解：
splay维护
注意是gcd
代码：
#include<bits/stdc++.h> using namespace std; #define Key_value ch[ch[root][1]][0] const int N=300010; char op[100]; int pre[N],ch[N][2],key[N],size[N],root,tot1,L,R,pos,_st,val; int sum0[N],sum1[N],st[N],s[N],tot2,a[N],status[N],n,q; int gcd(int a,int b) { if (!b)return a; else return gcd(b,a%b); } void NewNode(int &r,int father,int k,int _st) { if (tot2)r=s[tot2--]; else r=++tot1; pre[r]=father; ch[r][0]=ch[r][1]=0; key[r]=k; st[r]=_st; if (_st==0){sum0[r]=k;sum1[r]=0;} else {sum1[r]=k;sum0[r]=0;} size[r]=1; } void push_up(int r) { int lson=ch[r][0],rson=ch[r][1]; size[r]=size[lson]+size[rson]+1; sum0[r]=sum1[r]=0; sum0[r]=gcd(sum0[lson],sum0[rson]); sum1[r]=gcd(sum1[lson],sum1[rson]); if (st[r])sum1[r]=gcd(sum1[r],key[r]); else sum0[r]=gcd(sum0[r],key[r]); } void Build(int &x,int l,int r,int father) { if (l>r)return; int mid=(l+r)/2; NewNode(x,father,a[mid],status[mid]); Build(ch[x][0],l,mid-1,x); Build(ch[x][1],mid+1,r,x); push_up(x); } void Rotate(int x,int kind) { int y=pre[x]; ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; if (pre[y])ch[pre[y]][ch[pre[y]][1]==y] = x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; push_up(y); } void splay(int r,int goal) { while (pre[r]!=goal) { if (pre[pre[r]]==goal)Rotate(r,ch[pre[r]][0]==r); else { int y=pre[r],kind=ch[pre[y]][0]==y; if(ch[y][kind]==r) { Rotate(r,!kind); Rotate(r,kind); } else { Rotate(y,kind); Rotate(r,kind); } } } push_up(r); if (!goal)root=r; } int Get_kth(int r,int k) { int t=size[ch[r][0]]+1; if (t==k)return r; if (t>k)return Get_kth(ch[r][0],k); else return Get_kth(ch[r][1],k-t); } void Insert(int pos,int _val,int _st) { splay(Get_kth(root,pos+1),0); splay(Get_kth(root,pos+2),root); NewNode(Key_value,ch[root][1],_val,_st); push_up(ch[root][1]); push_up(root); } void erase(int r) { if(!r)return; s[++tot2] = r; erase(ch[r][0]); erase(ch[r][1]); } void Delete(int pos) { splay(Get_kth(root,pos),0); splay(Get_kth(root,pos+2),root); erase(Key_value); pre[Key_value] = 0; Key_value = 0; push_up(ch[root][1]); push_up(root); } void Change(int pos) { splay(Get_kth(root,pos),0); splay(Get_kth(root,pos+2),root); st[Key_value]^=1; push_up(Key_value); push_up(ch[root][1]); push_up(root); } void Modify(int pos,int _val) { splay(Get_kth(root,pos),0); splay(Get_kth(root,pos+2),root); key[Key_value]=_val; push_up(Key_value); push_up(ch[root][1]); push_up(root); } int Query(int L,int R,int _st) { int ans; splay(Get_kth(root,L),0); splay(Get_kth(root,R+2),root); if (!_st)ans=sum0[Key_value]; else ans=sum1[Key_value]; if (!ans)ans=-1; return ans; } int main() { while (~scanf("%d%d",&n,&q)) { root=tot1=tot2=0; ch[root][0]=ch[root][1]=size[root]=pre[root]=sum0[root]=sum1[root]=0; NewNode(root,0,0,0); NewNode(ch[root][1],root,0,0); for (int i=0;i<n;i++)scanf("%d%d",&a[i],&status[i]); Build(Key_value,0,n-1,ch[root][1]); push_up(ch[root][1]);push_up(root); while(q--) { scanf("%s",op); if (op[0]=='Q') { scanf("%d%d%d",&L,&R,&_st); printf("%d ",Query(L,R,_st)); } if (op[0]=='I') { scanf("%d%d%d",&pos,&val,&_st); Insert(pos,val,_st); } if (op[0]=='D') { scanf("%d",&pos); Delete(pos); } if (op[0]=='R') { scanf("%d",&pos); Change(pos); } if (op[0]=='M') { scanf("%d%d",&pos,&val); Modify(pos,val); } } } return 0; }