BZOJ1493:[NOI2007]项链工厂 Splay

思路:

脑补了半天发现还是不知道怎么上线段树,于是无脑Splay.

操作应该都非常容易实现吧.

对于每一个节点记录一下区间的左右端的颜色,自己的颜色以及颜色段数.

没什么好说的,详情见代码.

教训:

我得到区间是利用返回Splay中的一个点来实现的.

注意这个点并不是静态的.

所以得到之后立即将信息存下来.

否则再去得到别的区间的时候,这个点的信息会发生变化.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 500010
 
#define l ch[0]
#define r ch[1]
 
int a[N];
struct Node{
    Node*ch[2],*pa;
    int siz,num,c,col,lcol,rcol;
    bool rev;
    Node():siz(0),num(0),rev(0){}
     
    bool d(){return this==pa->ch[1];}
    inline void sc(Node*p,bool d){ch[d]=p,p->pa=this;}
}mem[N],*P=mem,Tnull,*null=&Tnull,*Root;
 
inline void covit(Node*p,int c){
    p->c=p->col=p->lcol=p->rcol=c;
    p->num=1;
}
inline void revit(Node*p){
    p->rev^=1,swap(p->lcol,p->rcol),swap(p->l,p->r);
}
inline void down(Node*p){
    if(p->rev){
        if(p->l!=null)revit(p->l);
        if(p->r!=null)revit(p->r);
        p->rev=0;
    }
    if(p->c!=0){
        if(p->l!=null)covit(p->l,p->c);
        if(p->r!=null)covit(p->r,p->c);
        p->c=0;
    }
}
inline void up(Node*p){
    p->siz=p->l->siz+1+p->r->siz;
    p->num=p->l->num+p->r->num+1;
    if(p->l!=null&&p->col==p->l->rcol)--p->num;
    if(p->r!=null&&p->col==p->r->lcol)--p->num;
    p->lcol=(p->l!=null)?p->l->lcol:p->col;
    p->rcol=(p->r!=null)?p->r->rcol:p->col;
}
Node*Newnode(int col){
    P->l=P->r=P->pa=null;
    P->siz=1,P->num=1,P->c=P->rev=0,P->col=P->lcol=P->rcol=col;return P++;
}
Node*Build(int tl,int tr){
    if(tl>tr)return null;
    int mid=(tl+tr)>>1;
    Node*q=Newnode(a[mid]);
    q->sc(Build(tl,mid-1),0);
    q->sc(Build(mid+1,tr),1);
    up(q);
    return q;
}
inline void Rot(Node*p){
    bool d=p->d();Node*fa=p->pa;
    down(fa),down(p);
    fa->pa->sc(p,fa->d()),fa->sc(p->ch[!d],d),p->sc(fa,!d);
    up(fa);
    if(fa==Root)Root=p;
}
inline void Splay(Node*p,Node*Anc=null){
    while(p->pa!=Anc){
        if(p->pa->pa==Anc)Rot(p);
        else Rot(p->d()==p->pa->d()?p->pa:p),Rot(p);
    }up(p);
}
inline Node*kth(int k){
    Node*re=Root;
    while(1){
        down(re);
        if(re->l->siz>=k)re=re->l;
        else if(k==re->l->siz+1)return re;
        else k-=re->l->siz+1,re=re->r;
    }
}
inline Node*get(int dl,int dr){
    Node*p=kth(dl);Splay(p);
    Node*q=kth(dr+2);Splay(q,p);
    return q->l;
}
inline Node*del(int dl,int dr){
    Node*p=get(dl,dr);
    p->pa->sc(null,0),up(p->pa),up(p->pa->pa);
    return p;
}
inline void cover(int dl,int dr,int c){
    covit(get(dl,dr),c);
}
inline void reverse(int dl,int dr){
    revit(get(dl,dr));
}
inline void insert(int ins,Node*x){
    Node*p=kth(ins);Splay(p);
    Node*q=kth(ins+1);Splay(q,p);
    q->sc(x,0),up(q),up(p);
}
 
inline void pre(){
    Root=Newnode(0);
    Node*p=Newnode(0);
    Root->sc(p,1),up(Root);
}
 
int main(){
    int n,Maxc;scanf("%d%d",&n,&Maxc);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
     
    pre(),insert(1,Build(1,n));
     
    int m;
    scanf("%d",&m);
    char qte[10];int x,y,c;
    while(m--){
        scanf("%s",qte);
         
        if(qte[0]=='R'){
            scanf("%d",&x);
             
            Node*p=del(n-x+1,n);
            insert(1,p);
        }
         
        if(qte[0]=='F'){
            reverse(2,n);
        }
         
        if(qte[0]=='S'){
            scanf("%d%d",&x,&y);
            if(x!=y){
                 
                if(x>y)swap(x,y);
             
                Node*getx=del(x,x),*gety=del(y-1,y-1);
                insert(x,gety),insert(y,getx);
            }
        }
         
        if(qte[0]=='P'){
            scanf("%d%d%d",&x,&y,&c);
             
            if(x<=y)cover(x,y,c);
            else cover(x,n,c),cover(1,y,c);
        }
         
        if(strlen(qte)==1&&qte[0]=='C'){
            Node*re=get(1,n);
            printf("%d\n",re->num==1?1:re->num-(re->lcol==re->rcol));
        }
         
        if(qte[0]=='C'&&qte[1]=='S'){
            scanf("%d%d",&x,&y);
            if(x<=y){
                Node*re=get(x,y);
                printf("%d\n",re->num);
            }
            else{
                int re=0,rcol,lcol;
                Node*re1=get(x,n);re+=re1->num,rcol=re1->rcol;
                Node*re2=get(1,y);re+=re2->num,lcol=re2->lcol;
                printf("%d\n",re-(rcol==lcol));
            }
        }
    }
     
    return 0;
}