【BZOJ1493】【NOI2007】项链工厂

    这是一道线段树。用Splay的话应该很好打但是不知道NOI评测时能不能过。

    对于Rotate操作和Flip操作，不修改线段树上点的位置，在外面放标记rev和pos1表示项链是否被反转过以及项链的位置1上是哪个珠子。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=500010;
 
struct Segment_Tree
{
    int lc[maxn<<2],rc[maxn<<2],cs[maxn<<2];
    int tag_same[maxn<<2],same[maxn<<2];
    int pos1,rev;
    int n;
    int _l,_r,_v;
 
    #define ls (o<<1)
    #define rs ((o<<1)|1)
    #define mid ((l+r)>>1)
 
    int GetPos(int x) {return rev==0?((pos1+(x-1)+n-1)%n+1):((pos1-(x-1)+n-1)%n+1);}
 
    void Update(int o)
    {
        lc[o]=lc[ls];
        rc[o]=rc[rs];
        cs[o]=cs[ls]+cs[rs];
        if (rc[ls]==lc[rs]) cs[o]--;
    }
     
    void Mark_Same(int o,int vsame)
    {
        lc[o]=rc[o]=vsame;
        cs[o]=1;
        tag_same[o]=1;
        same[o]=vsame;
    }
 
    void Push_Down(int o)
    {
        if (tag_same[o])
        {
            Mark_Same(ls,same[o]);
            Mark_Same(rs,same[o]);
            tag_same[o]=0;
        }
    }
 
    void Build_Tree(int o,int l,int r,int *color)
    {
        if (l==r) {lc[o]=rc[o]=color[l];cs[o]=1;return;}
        Build_Tree(ls,l,mid,color);
        Build_Tree(rs,mid+1,r,color);
        Update(o);
    }
 
    void Change(int o,int l,int r)
    {
        if (_l<=l && r<=_r) {Mark_Same(o,_v);return;}
        Push_Down(o);
        if (_l<=mid) Change(ls,l,mid);
        if (_r> mid) Change(rs,mid+1,r);
        Update(o);
    }
 
    int Query(int o,int l,int r,int &nlc,int &nrc)
    {
        if (_l<=l && r<=_r) {nlc=lc[o];nrc=rc[o];return cs[o];}
        Push_Down(o);
        int res=0,nlrc,nrlc;
        if (_r>mid && _l<=mid) {res=Query(ls,l,mid,nlc,nlrc)+Query(rs,mid+1,r,nrlc,nrc);res-=(nlrc==nrlc);}
        else if (_l>mid) res=Query(rs,mid+1,r,nlc,nrc);
        else res=Query(ls,l,mid,nlc,nrc);
        Update(o);
        return res;
    }
 
    void Rotate(int x) {if (!rev) pos1=(pos1-x+n-1)%n+1;else pos1=(pos1+x-1)%n+1;}
    void Flip() {_l=1,_r=n;rev^=1;}
    void Swap(int x,int y)
    {
        x=GetPos(x);
        y=GetPos(y);
        int nlc,nrc,v1,v2;
        _l=x;_r=x;
        (void)Query(1,1,n,nlc,nrc);v1=nlc;
        _l=y;_r=y;
        (void)Query(1,1,n,nlc,nrc);v2=nrc;
        _v=v2,_l=_r=x;
        Change(1,1,n);
        _v=v1,_l=_r=y;
        Change(1,1,n);
    }
    void Paint(int x,int y,int tc)
    {
        x=GetPos(x);
        y=GetPos(y);
        if (rev) swap(x,y);
        _v=tc;
        if (x<=y) _l=x,_r=y,Change(1,1,n);
        else _l=x,_r=n,Change(1,1,n),_l=1,_r=y,Change(1,1,n);
    }
    int Count(int x,int y)
    {
        x=GetPos(x);
        y=GetPos(y);
        if (rev) swap(x,y);
        int res=0,nlc,nrc,temp;
        if (x<=y)
        {
            _l=x;_r=y;
            res=Query(1,1,n,nlc,nrc);
            return res;
        }
        else
        {
            _l=x,_r=n;
            res+=Query(1,1,n,temp,nrc);
            _l=1,_r=y;
            res+=Query(1,1,n,nlc,temp);
            if (nlc==nrc) res--;
            return res;
        }
    }
}T;
 
int n,c,q;
char ctr[10];
int temp[maxn];
 
void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}
 
int main()
{
    read(n),read(c);
    for (int i=1;i<=n;i++) read(temp[i]);
    T.Build_Tree(1,1,n,temp);T.n=n;T.pos1=1;
    read(q);
    while (q--)
    {
        int x,y,tc;
        scanf("%s",ctr);
        if (ctr[0]=='R') read(x),T.Rotate(x);
        else if (ctr[0]=='F') T.Flip();
        else if (ctr[0]=='S') read(x),read(y),T.Swap(x,y);
        else if (ctr[0]=='P') read(x),read(y),read(tc),T.Paint(x,y,tc);
        else if (ctr[1]=='S') read(x),read(y),printf("%d\n",T.Count(x,y));
        else printf("%d\n",T.cs[1]-(T.cs[1]>1 && T.lc[1]==T.rc[1]));
    }
    return 0;
}