BZOJ-1493: [NOI2007]项链工厂

Description

一条项链包含 N 个珠子，每个珠子的颜色是 1，2，…，c 中的一种。项链被固定在一个平板上，平板的某个位置被标记位置 1 ，按顺时针方向其他位置被记为 2，3，…，N。

你将要编写的软件系统应支持如下命令：

N≤500000 ，Q≤500000，c≤1000

splay慢的要死。
有几个需要特判的地方：
1.pushup需要将端点先赋值为当前节点颜色，再判断左右儿子。
2.项链当只有一个颜色的时候，不需要减去端点的。
3.交换两个节点的时候，将其旋转到根和右儿子。需要更改fa指针。
4.写的好长啊。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,c;
int col[501000];
char st[50];
inline int read()
{
    char ch=getchar(); int re=0;
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
        re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re;
}
struct node
{
    node *fa,*c[2];
    int siz,cl,cm,cr,num,lz;
    bool tur;
    node(int x);
    void reverse();
    void ad_col(int x);
    void pushup();
    void pushdown();
}*null=new node(0),*root;
node::node(int x)
{
    fa=c[0]=c[1]=null;
    cl=cm=cr=x;
    siz=num=null?1:0;
    tur=0; lz=0;
}
void node::reverse() {swap(c[0],c[1]); swap(cl,cr); tur^=1;}
void node::ad_col(int x){cl=cm=cr=x; lz=x; num=1;}
void node::pushdown()
{
    if(tur)
    {
        if(c[0]!=null) c[0]->reverse();
        if(c[1]!=null) c[1]->reverse();
        tur=0;
    }
    if(lz)
    {
        if(c[0]!=null) c[0]->ad_col(lz);
        if(c[1]!=null) c[1]->ad_col(lz);
        lz=0;
    }
}
void node::pushup()
{
    siz=c[0]->siz+c[1]->siz+1; num=1; cl=cr=cm;
    if(c[0]!=null)
    {
        cl=c[0]->cl;
        num+=c[0]->num-(c[0]->cr==cm);
    }
    if(c[1]!=null)
    {
        cr=c[1]->cr;
        num+=c[1]->num-(c[1]->cl==cm);
    }
}
node *build(int l,int r)
{
    if(r<l) return null;
    int mid=l+r>>1;
    node *re=new node(col[mid]);
    re->c[0]=build(l,mid-1); re->c[1]=build(mid+1,r);
    re->c[0]->fa=re; re->c[1]->fa=re;
    re->pushup(); return re;
}
void initialize()
{
    root=new node(0);
    root->c[1]=new node(0);
    root->c[1]->fa=root;
    root->c[1]->c[0]=build(1,n);
    root->c[1]->c[0]->fa=root->c[1];
    root->c[1]->pushup();
    root->pushup();
}
void rotate(node *x)
{
    node *y=x->fa; bool l=(x==y->c[1]),r=l^1;
    y->c[l]=x->c[r]; x->c[r]->fa=y;
    x->c[r]=y; x->fa=y->fa;
    if(y==y->fa->c[0]) y->fa->c[0]=x;
    else y->fa->c[1]=x;
    y->fa=x; y->pushup(); x->pushup();
    if(y==root) root=x;
}
void splay(node *x,node *tar)
{
    while(x->fa!=tar)
    {
        node *y=x->fa,*z=y->fa;
        if(z==tar){rotate(x); break;}
        if((x==y->c[0])^(y==z->c[0])) rotate(x);
        else rotate(y); rotate(x);
    }
}
void find(node *x,int y,node *z)
{
    while(1)
    {
        x->pushdown();
        int tmp=x->c[0]->siz;
        if(y<=tmp) x=x->c[0];
        else
        {
            y-=tmp+1;
            if(!y) break;
            x=x->c[1];
        }
    }
    splay(x,z);
}
void Rotate()
{
    int x; scanf("%d",&x); x%=n;
    find(root,n-x+1,null); find(root,n+2,root);
    node *p=root->c[1]->c[0];
    root->c[1]->c[0]=null;
    root->c[1]->pushup();
    root->pushup();
    find(root,1,null); find(root,2,root);
    root->c[1]->c[0]=p;
    p->fa=root->c[1];
    root->c[1]->pushup();
    root->pushup();
}
void Flip()
{
    find(root,2,null); find(root,n+2,root);
    root->c[1]->c[0]->reverse();
    root->c[1]->pushup();
    root->pushup();
}
void Swap()
{
    int x,y; scanf("%d%d",&x,&y); if(x>y) swap(x,y);
    if(x==y) return ;
    find(root,x+1,null); find(root,y+1,root);
    node *xx=root,*yy=root->c[1];
    xx->c[1]=yy->c[1]; yy->c[1]->fa=xx;
    yy->c[1]=xx; xx->fa=yy; yy->fa=null;
    swap(xx->c[0],yy->c[0]); yy->c[0]->fa=yy;
    if(xx->c[0]!=null) xx->c[0]->fa=xx;
    xx->pushup(); yy->pushup(); root=yy;
}
void Paint()
{
    int l,r,x; scanf("%d%d%d",&l,&r,&x);
    if(l<=r)
    {
        find(root,l,null); find(root,r+2,root);
        root->c[1]->c[0]->ad_col(x);
        root->c[1]->pushup();
        root->pushup();
    }
    else
    {
        find(root,1,null); find(root,r+2,root);
        root->c[1]->c[0]->ad_col(x);
        root->c[1]->pushup();
        root->pushup();
        find(root,l,null); find(root,n+2,root);
        root->c[1]->c[0]->ad_col(x);
        root->c[1]->pushup();
        root->pushup();
    }
}
void Count()
{
    find(root,1,null); find(root,n+2,root);
    if(root->c[1]->c[0]->cl==root->c[1]->c[0]->cr&&root->c[1]->c[0]->num!=1)
        printf("%d\n",root->c[1]->c[0]->num-1);
    else printf("%d\n",root->c[1]->c[0]->num);
}
void CouSeg()
{
    int x,y; scanf("%d%d",&x,&y);
    if(x<=y)
    {
        find(root,x,null); find(root,y+2,root);
        printf("%d\n",root->c[1]->c[0]->num);
    }
    else
    {
        find(root,1,null); find(root,y+2,root);
        int tmp=root->c[1]->c[0]->cl,num=root->c[1]->c[0]->num;
        find(root,x,null); find(root,n+2,root);
        num+=root->c[1]->c[0]->num;
        if(tmp==root->c[1]->c[0]->cr) num--;
        printf("%d\n",num);
    }
}
int main()
{
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++) col[i]=read();
    initialize();
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",st);
        if(strlen(st)==2)CouSeg();
        else
        {
            switch(st[0])
            {
                case 'R':Rotate(); break;
                case 'F':Flip(); break;
                case 'S':Swap(); break;
                case 'P':Paint(); break;
                case 'C':Count(); break;
            }
        }
    }
    return 0;
}