ZOJ 3765 Lights （SPLAY）

gcd[x] =GCD( GCD( gcd[ls],gcd[rs]),val[x]) );

注意判断没有亮灯状态的情况

#include 
  
   
#include 
   
     #define inf 0x3f3f3f3f #define maxn 222222 #define keyTree (ch[ch[root][1]][0]) using namespace std; typedef long long LL; int S[maxn],que[maxn],ch[maxn][2],pre[maxn],siz[maxn]; int root,top1,top2; int gcd0[maxn],gcd1[maxn],st[maxn],a[maxn],aa[maxn],val[maxn]; int gcd(int a,int b) { if(a==-1 && b==-1)return -1; else if(a==-1 && b!=-1)return b; else if(a!=-1 && b==-1)return a; if(b == 0)return a; else return gcd(b,a%b); } void New(int &x,int PRE,int v,int ST) { if(top2)x=S[--top2]; else x=++top1; ch[x][0]=ch[x][1]=0; siz[x]=1; pre[x]=PRE; st[x]=ST; val[x]=v; if(ST) { gcd1[x]=v; gcd0[x]=-1; } else { gcd0[x]=v; gcd1[x]=-1; } } void pushup(int x) { siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1; int ls=ch[x][0]; int rs=ch[x][1]; gcd1[x]=gcd(gcd1[ls],gcd1[rs]); if(st[x]) gcd1[x]=gcd(gcd1[x],val[x]); gcd0[x]=gcd(gcd0[ls],gcd0[rs]); if(!st[x]) gcd0[x]=gcd(gcd0[x],val[x]); } void pushdown(int x) { } void build(int &x,int s,int e,int f) { if(s>e)return; int mid=(s+e)>>1; New(x,f,a[mid],aa[mid]); if(s
    
     mid)build(ch[x][1],mid+1,e,x); pushup(x); } void Rotate(int x,int kind) { int y=pre[x]; pushdown(x); pushdown(y); 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; pushup(y); } void Splay(int x,int goal) { pushdown(x); while(pre[x]!=goal) { if(pre[pre[x]]==goal) Rotate(x,ch[pre[x]][0]==x); else { int y=pre[x]; int kind=ch[pre[y]][0]==y; if(ch[y][kind]==x){ Rotate(x,!kind); Rotate(x,kind); } else { Rotate(y,kind); Rotate(x,kind); } } } pushup(x); if(goal==0)root=x; } void RotateTo(int k,int goal) { int r=root; pushdown(r); while(siz[ch[r][0]]!=k) { if(k