好吧，不得不承认，经过一个寒假的颓废啥都忘了。。
一道裸的splay，但是比赛的时候我一直觉得用splay维护gcd会不会出错。。。。因为我居然觉得旋转过程中gcd无法正确维护。。。。
思路：splay节点信息
on:节点是否是开灯状态
val0:该节点关灯时的值，如果该节点灯开着，那么val0=0,不影响结果。
val1:该节点开灯时的值，如果该节点灯关着，那么val1=0,不影响结果。
gcd0:以该节点为根的子树中所有状态为关的灯的gcd
gcd1:以该节点为根的子树中所有状态为开的灯的gcd
num[0]:以该节点为根的子树有多少个状态为关的灯
num[1]:以该节点为根的子树有多少个状态为开的灯
看来这个月要好好复习了。。。。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 500000+100
#define inf 0x3f3f3f3f
inline int max(int a,int b){return a>b?a:b;}
int gcd(int a,int b)
{
if(a<b) {int t=a;a=b;b=t;}
return (b==0?a:gcd(b,a%b));
}
struct SplayTree {
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]
int root;//根节点
int fa[N];//父亲结点
int ch[N][2];//孩子结点
int sz[N];//以结点i为子树的结点数
int cnt;
int val0[N],val1[N];
int on[N];
int gcd0[N],gcd1[N];
int data[N],state[N];
int num[N][2];
void pushup(int x)
{
sz[x]=1+sz[LC]+sz[RC];//如果左子树为空，则LC=0,而sz[0]=0,即如果结点某个结点的子节点不存在，则指向空结点0，空节点的sz=0，不会造成错误
gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
num[x][0]=num[LC][0]+num[RC][0]+1-on[x];
num[x][1]=num[LC][1]+num[RC][1]+on[x];
}
void rotate(int x, bool f) //旋转
{
int y=fa[x];
int z=fa[y];
ch[y][!f]=ch[x][f];
fa[ch[x][f]]=y;
fa[x]=z;
if(z)
{
ch[z][ch[z][1]==y]=x;
}
ch[x][f]=y;
fa[y]=x;
pushup(y);
}
void splay(int x, int g) //把结点x转到结点g下
{
int y=fa[x];
while (y!=g)
{
int z=fa[y];
bool f=(ch[y][0]==x);
if (z!=g && f==(ch[z][0]==y))
{
rotate(y,f);
}
rotate(x,f);
y=fa[x];
}
pushup(x);
if(g==0)
{
root=x;
}
}
void rotateto(int k,int g) { //把第k个结点转到结点g下,从第0个开始，因为有附加结点
int x=root;
while (sz[LC]!=k)
{
if (k<sz[LC])
{
x=LC;
} else
{
k-=(sz[LC]+1);
x=RC;
}
}
splay(x,g);
}
void newNode(int &x,int c,int flag)
{
x=++cnt;
on[x]=flag;
num[x][flag]=1;num[x][1-flag]=0;
if(!flag) val0[x]=c,val1[x]=0;
else val1[x]=c,val0[x]=0;
LC=RC=fa[x]=0;
gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
sz[x]=1;
}
void makeTree(int &x,int l,int r,int f)
{
if (l>r)
{
return;
}
int m=(l+r)>>1;
newNode(x,data[m],state[m]); /*num[m]权值改成题目所需的*/
makeTree(LC,l,m-1,x);
makeTree(RC,m + 1,r,x);
fa[x]=f;
pushup(x);//建立树的时候，从下往上依次pushup
}
void init(int n)
{
cnt=0;
ch[0][0]=ch[0][1]=fa[0]=sz[0]=num[0][0]=num[0][1]=val0[0]=on[0]=val1[0]=gcd0[0]=gcd1[0]=0;//0结点是空节点，代表没有
//为了方便处理边界,加两个边界顶点
newNode(root,0,0);
newNode(ch[root][1],0,0);//这两个边界结点的值不影响正常求解
fa[cnt]=root;
sz[root]=2;
makeTree(KT,1,n,ch[root][1]);
pushup(ch[root][1]);
pushup(root);
}
int query(int l,int r,int flag)
{
rotateto(l-1,0);
rotateto(r+1,root);
if(num[KT][flag]==0) return -1;
return (flag==1?gcd1[KT]:gcd0[KT]);
}
void insert(int id,int v,int flag)
{
rotateto(id,0);
rotateto(id+1,root);
int x=ch[root][1];
newNode(LC,v,flag);
fa[LC]=x;
pushup(x);
pushup(root);
}
void remove(int id)
{
rotateto(id-1,0);
rotateto(id+1,root);
int x=ch[root][1];
//fa[LC]=0;
LC=0;
pushup(x);
pushup(root);
}
void swap2(int &a,int &b)
{
int t=a;a=b;b=t;
}
void swap(int x)
{
on[x]=1-on[x];
swap2(val0[x],val1[x]);
gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
num[x][0]=num[LC][0]+num[RC][0]+(1-on[x]);
num[x][1]=num[LC][1]+num[RC][1]+on[x];
}
void rev(int id)
{
rotateto(id-1,0);
rotateto(id+1,root);
int x=ch[root][1];
swap(KT);
pushup(x);
pushup(root);
}
void modify(int id,int v)
{
rotateto(id-1,0);
rotateto(id+1,root);
int x=ch[root][1];
if(on[LC]==1) val1[LC]=v;
else val0[LC]=v;
gcd0[LC]=gcd(gcd(gcd0[ch[LC][0]],gcd0[ch[LC][1]]),val0[LC]);
gcd1[LC]=gcd(gcd(gcd1[ch[LC][0]],gcd1[ch[LC][1]]),val1[LC]);
pushup(x);
pushup(root);
return;
}
void print(int x)
{
if(sz[x]==0) return;
print(LC);
printf("on:%d val0:%d val1:%d gcd0:%d gcd1:%d\n",on[x],val0[x],val1[x],gcd0[x],gcd1[x]);
print(RC);
}
void debug(int x)
{
print(x);
printf("\n");
}
}spt;
int main()
{
int i,j;
int n,m;
while(~scanf("%d%d",&n,&m))
{
for(i=1;i<=n;i++)
scanf("%d%d",&spt.data[i],&spt.state[i]);
spt.init(n);
char com[5];
int a,b,state;
while(m--)
{
scanf("%s",com);
if(com[0]=='Q')
{
scanf("%d%d%d",&a,&b,&state);
printf("%d\n",spt.query(a,b,state));
}
if(com[0]=='I')
{
scanf("%d%d%d",&a,&b,&state);
spt.insert(a,b,state);
}
if(com[0]=='D')
{
scanf("%d",&a);
spt.remove(a);
}
if(com[0]=='R')
{
scanf("%d",&a);
spt.rev(a);
}
if(com[0]=='M')
{
scanf("%d%d",&a,&b);
spt.modify(a,b);
}
//spt.debug(spt.root);
}
}
return 0;
}