ZOJ 3765 Lights （SPLAY）

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

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

#include <cstdio>
#include <iostream>
#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][0],s,mid-1,x);
    if(e>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<siz[ch[r][0]])
        {
            r=ch[r][0];
        }
        else
        {
            k-=siz[ch[r][0]]+1;
            r=ch[r][1];
        }
        pushdown(r);
    }
    Splay(r,goal);
}
void erase(int x)
{
    int y=pre[x];
    int head=0,tail=0;
    for(que[tail++]=x;head<tail;head++)
    {
        S[top2++]=que[head];
        if(ch[que[head]][0])que[tail++]=ch[que[head]][0];
        if(ch[que[head]][1])que[tail++]=ch[que[head]][1];
    }
    ch[y][ch[y][1]==x]=0;
    pushup(y);
}

void init(int n)
{
    root=top1=top2=0;
    ch[0][0]=ch[0][1]=siz[0]=pre[0]=0;
    st[0]=0;
    gcd0[0]=gcd1[0]=-1;

    New(root,0,-1,0);
    New(ch[root][1],root,-1,0);

    siz[root]=2;

    for(int i=0;i<n;i++)scanf("%d%d",&a[i],&aa[i]);
    build(keyTree,0,n-1,ch[root][1]);
    pushup(ch[root][1]);
    pushup(root);
}

int main()
{
    int n,m;
    char str[5];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init(n);
        int l,r,op;
        while(m--)
        {
            scanf("%s",str);
            if(str[0]==‘Q‘)
            {
                scanf("%d%d%d",&l,&r,&op);
                RotateTo(l-1,0);
                RotateTo(r+1,root);

                if(op==1)printf("%d\n",gcd1[keyTree]);
                else printf("%d\n",gcd0[keyTree]);
            }
            else if(str[0]==‘I‘)
            {
                scanf("%d%d%d",&l,&r,&op);
                RotateTo(l,0);
                RotateTo(l+1,root);

                New(keyTree,ch[root][1],r,op);
                pushup(ch[root][1]);
                pushup(root);
            }
            else if(str[0]==‘D‘)
            {
                scanf("%d",&l);
                RotateTo(l-1,0);
                RotateTo(l+1,root);

                pre[keyTree]=0;
                keyTree=0;
                pushup(ch[root][1]);
                pushup(root);
            }
            else if(str[0]==‘R‘)
            {
                scanf("%d",&l);
                RotateTo(l-1,0);
                RotateTo(l+1,root);

                st[keyTree]^=1;
                if(st[keyTree])
                {
                    gcd0[keyTree]=-1;
                    gcd1[keyTree]=val[keyTree];
                }
                else
                {
                    gcd0[keyTree]=val[keyTree];
                    gcd1[keyTree]=-1;
                }

                pushup(ch[root][1]);
                pushup(root);
            }
            else
            {
                scanf("%d%d",&l,&r);
                RotateTo(l-1,0);
                RotateTo(l+1,root);

                val[keyTree]=r;
                if(st[keyTree])
                {
                    gcd0[keyTree]=-1;
                    gcd1[keyTree]=val[keyTree];
                }
                else
                {
                    gcd0[keyTree]=val[keyTree];
                    gcd1[keyTree]=-1;
                }

                pushup(ch[root][1]);
                pushup(root);
            }
        }
    }
    return 0;
}

ZOJ 3765 Lights （SPLAY）,布布扣,bubuko.com

ZOJ 3765 Lights （SPLAY）

原文：http://blog.csdn.net/u010709592/article/details/23794003