zoj3765

题解：

splay维护

注意是gcd

代码：

#include<bits/stdc++.h>

using namespace std;

#define Key_value ch[ch[root][1]][0]

const int N=;

char op[];

int pre[N],ch[N][],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][]=ch[r][]=;

    key[r]=k;

    st[r]=_st;

    if (_st==){sum0[r]=k;sum1[r]=;}

    else {sum1[r]=k;sum0[r]=;}

    size[r]=;

}

void push_up(int r)

{

    int lson=ch[r][],rson=ch[r][];

    size[r]=size[lson]+size[rson]+;

    sum0[r]=sum1[r]=;

    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)/;

    NewNode(x,father,a[mid],status[mid]);

    Build(ch[x][],l,mid-,x);

    Build(ch[x][],mid+,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]][]==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]][]==r);

        else

         {

            int y=pre[r],kind=ch[pre[y]][]==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][]]+;

    if (t==k)return r;

    if (t>k)return Get_kth(ch[r][],k);

    else return Get_kth(ch[r][],k-t);

}

void Insert(int pos,int _val,int _st)

{

    splay(Get_kth(root,pos+),);

    splay(Get_kth(root,pos+),root);

    NewNode(Key_value,ch[root][],_val,_st);

    push_up(ch[root][]);

    push_up(root);

}

void erase(int r)

{

    if(!r)return;

    s[++tot2] = r;

    erase(ch[r][]);

    erase(ch[r][]);

}

void Delete(int pos)

{

    splay(Get_kth(root,pos),);

    splay(Get_kth(root,pos+),root);

    erase(Key_value);

    pre[Key_value] = ;

    Key_value = ;

    push_up(ch[root][]);

    push_up(root);

}

void Change(int pos)

{

    splay(Get_kth(root,pos),);

    splay(Get_kth(root,pos+),root);

    st[Key_value]^=;

    push_up(Key_value);

    push_up(ch[root][]);

    push_up(root);

}

void Modify(int pos,int _val)

{

    splay(Get_kth(root,pos),);

    splay(Get_kth(root,pos+),root);

    key[Key_value]=_val;

    push_up(Key_value);

    push_up(ch[root][]);

    push_up(root);

}

int Query(int L,int R,int _st)

{

    int ans;

    splay(Get_kth(root,L),);

    splay(Get_kth(root,R+),root);

    if (!_st)ans=sum0[Key_value];

    else ans=sum1[Key_value];

    if (!ans)ans=-;

    return ans;

}

int main()

{

    while (~scanf("%d%d",&n,&q))

     {

        root=tot1=tot2=;

        ch[root][]=ch[root][]=size[root]=pre[root]=sum0[root]=sum1[root]=;

        NewNode(root,,,);

        NewNode(ch[root][],root,,);

        for (int i=;i<n;i++)scanf("%d%d",&a[i],&status[i]);

        Build(Key_value,,n-,ch[root][]);

        push_up(ch[root][]);push_up(root);

        while(q--)

         {

            scanf("%s",op);

            if (op[]=='Q')

             {

                scanf("%d%d%d",&L,&R,&_st);

                printf("%d\n",Query(L,R,_st));

             }

            if (op[]=='I')

             {

                scanf("%d%d%d",&pos,&val,&_st);

                Insert(pos,val,_st);

             }

            if (op[]=='D')

             {

                scanf("%d",&pos);

                Delete(pos);

             }

            if (op[]=='R')

             {

                scanf("%d",&pos);

                Change(pos);

             }

            if (op[]=='M')

             {

                scanf("%d%d",&pos,&val);

                Modify(pos,val);

             }

         }

     }

    return ;

}