$Description$

写一种数据结构，支持区间染色，区间翻转，区间旋转，区间查询颜色，单点修改颜色
$对于100\%的数据，N\le 500000，Q\le 500000，c\le 100$

---

$Solution$

Splay裸题

我们可以用线段树搞

染色、查询、修改线段树$soeasy$啦

重点是旋转和翻转

旋转的话我们可以对于每个对应的编号求出其转后的编号即可，没啥影响

翻转则需要每次特殊处理，注意到翻转只会相对1转，所以直接稍微处理一下环形的细节即可

时间复杂度：$O(nlogn)$

---

$Code$

#include<cstdio>
#include<cctype>
#include<algorithm>
#define N 500010
using namespace std;int n,C,m,a[N],p;
bool rev;
inline int read()
{int f=0,d=1;char c;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
inline void Seg(int &x)
{if(rev) x=n-x+2;x-=p;while(x<1) x+=n;while(x>n) x-=n;return;
}
struct xds
{#define lson k<<1#define rson k<<1|1int sum[N<<2],lc[N<<2],rc[N<<2],col[N<<2];inline void down(int k){if(!col[k]) return;lc[lson]=rc[lson]=lc[rson]=rc[rson]=col[lson]=col[rson]=col[k];sum[lson]=sum[rson]=1;col[k]=0;return;}inline void up(int k){sum[k]=sum[lson]+sum[rson];if(rc[lson]==lc[rson]) sum[k]--;lc[k]=lc[lson];rc[k]=rc[rson];return;}inline void build(int k,int l,int r){col[k]=0;if(l==r){lc[k]=rc[k]=read();sum[k]=1;return;}int mid=l+r>>1;build(lson,l,mid);build(rson,mid+1,r);up(k);return;}inline void modify(int x,int y,int v,int k=1,int l=1,int r=n){if(x<=l&&y>=r){col[k]=v;lc[k]=rc[k]=v;sum[k]=1;return;}down(k);int mid=l+r>>1;if(x<=mid) modify(x,y,v,lson,l,mid);if(y>mid) modify(x,y,v,rson,mid+1,r);up(k);return;}inline int query(int x,int y,int k=1,int l=1,int r=n){if(x<=l&&y>=r) return sum[k];down(k);int mid=l+r>>1;int ans=0;if(x<=mid) ans+=query(x,y,lson,l,mid);if(y>mid) ans+=query(x,y,rson,mid+1,r);if(x<=mid&&y>mid&&rc[lson]==lc[rson]) ans--;return ans;}inline int queryC(int x,int k=1,int l=1,int r=n){if(l==r&&r==x) return lc[k];down(k);int mid=l+r>>1;if(x<=mid) return queryC(x,lson,l,mid);else return queryC(x,rson,mid+1,r);}#undef lson#undef rson
}Tree;
signed main()
{n=read();C=read();Tree.build(1,1,n);m=read();for(char op[5];m--;){scanf("%s",op);int x,y;if(op[0]=='C')if(op[1]){x=read(),y=read();Seg(x);Seg(y);//得到新的坐标点if(rev) swap(x,y);//翻转if(x<=y){int ans=Tree.query(x,y);if(x==1&&y==n&&Tree.lc[1]==Tree.rc[1]&&ans>1) ans--;//边界连起来处理环形情况printf("%d\n",ans);}else{int ans=Tree.query(x,n)+Tree.query(1,y);if(Tree.lc[1]==Tree.rc[1]) ans--;//越过一圈处理printf("%d\n",ans);}continue;}else{int ans=Tree.query(1,n);if(Tree.lc[1]==Tree.rc[1]&&ans>1) ans--;printf("%d\n",ans);continue;}if(op[0]=='R')//区间旋转{x=read();if(rev) p-=x;else p+=x;while(p<0) p+=n;while(p>n) p-=n;continue;}if(op[0]=='F') {rev^=1;continue;}//区间翻转if(op[0]=='S')//交换两点{x=read();y=read();Seg(x);Seg(y);//得到原坐标int xc=Tree.queryC(x),yc=Tree.queryC(y);//get颜色Tree.modify(x,x,yc);Tree.modify(y,y,xc);//单点染色continue;}if(op[0]=='P')//区间染色{x=read();y=read();int v=read();Seg(x);Seg(y);if(rev) swap(x,y);if(x<=y) Tree.modify(x,y,v);else Tree.modify(x,n,v),Tree.modify(1,y,v);continue;}}
}