提交地址：http://www.lydsy.com/JudgeOnline/problem.php?id=1493
题目大意：给一个数列，进行一系列操作。包括旋转，翻转，改变等操作，以及查询颜色段数。
题目分析：数列中元素的相对位置没有改变，因此不需要用splay去做，而是可以用线段树解决这类问题。
旋转操作直接改变变量rotate，翻转操作用异或即可。每次询问先利用rotate求出当前1号位是谁，这样可以根据翻转标记确定区间。如果区间跨越n，那么合并的时候要考虑左边一段的右端和右边一段的左端。相同的时候答案要减少1.
对于swap操作，由于是单点的，可以暴力在树上做。
这题以我的代码水平来说比较难打。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn = ;
struct node{
int lazy;
int lft,rgt,tot,full;
}t[maxn<<];
int n,c;
int x[maxn];
int fz,rt; // fanzhuan rotate
int tl,tr; void push_down(int now){
t[now<<].lazy = t[now<<|].lazy = t[now].lazy;
t[now].lft = t[now].rgt = t[now].lazy; t[now].tot = ;
t[now].lazy = ;t[now].full = ;
} void push_up(int now){
int L=(now<<),R = L+;
if(t[now].lazy)push_down(now);
if(t[L].lazy)push_down(L); if(t[R].lazy) push_down(R);
t[now].lft = t[L].lft; t[now].rgt = t[R].rgt;
t[now].tot = t[L].tot + t[R].tot;
if(t[L].rgt == t[R].lft) t[now].tot--;
if(t[L].full && t[R].full && t[L].rgt == t[R].rgt) t[now].full=;
else t[now].full = ;
} void build_tree(int l,int r,int now){
if(l == r){
t[now].lazy = ; t[now].lft = x[l]; t[now].rgt = x[l];
t[now].tot = ;t[now].full = ;
}else{
int mid = (l+r>>);int L=(now<<),R = L+;
build_tree(l,mid,L); build_tree(mid+,r,R);
push_up(now);
}
} void read(){
scanf("%d%d",&n,&c);
for(int i=;i<=n;i++){
scanf("%d",&x[i]);
}
build_tree(,n,);
} void Rotate(){
int now; scanf("%d",&now);
if(fz == ) rt += (n-now);
else rt += now;
rt %= n;
} int get_ans(int l,int r,int now){
if(now == ) tl = ,tr = n;
if(t[now].lazy) push_down(now);
if(tl > r || tr < l) return ;
if(tl >= l && tr <= r) return t[now].tot;
int mid = (tl+tr) / ;
int ans = ;
int tmp = tr; tr=mid;
int nnow = get_ans(l,r,now<<);
ans += nnow;
tr = tmp;tmp = tl; tl = mid+;
int know = get_ans(l,r,now<<|);
ans += know;
tl = tmp;
if(tr-tl!=&&t[now<<].rgt == t[now<<|].lft&&nnow&&know) ans--;
push_up(now);
return ans;
} int get_color(int ord,int now){
if(now == ) tl = ,tr = n;
if(t[now].lazy) {push_down(now);return t[now].lft;}
if(tl == tr) return t[now].lft;
int mid = (tl+tr)/;
int ans;
if(mid >= ord){tr = mid; ans = get_color(ord,now<<);}
else {tl = mid+; ans = get_color(ord,now<<|);}
push_up(now);
return ans;
} void Tpaint(int l,int r,int now,int xc){
if(now == ) tl = ,tr = n;
if(t[now].lazy) {push_down(now);}
if(tl > r || tr < l) return;
if(tl >= l && tr <= r) {t[now].lazy = xc;push_down(now);return;}
int mid = (tl+tr)/;
int tmp = tr;tr = mid;
Tpaint(l,r,now<<,xc);
tr = tmp; tmp = tl; tl = mid+;
Tpaint(l,r,now<<|,xc);
tl = tmp;
push_up(now);
} int cnt;
void Count(){
int l,r,flag=,flag2=;
char ch = getchar();
cnt++;
if(ch != 'S') {
l = ,r=n;
int ans = t[].tot-(t[].lft == t[].rgt && t[].full==);
printf("%d\n",ans);
return;
}else {
scanf("%d%d",&l,&r);
}
int st = (-rt); if(st <= ) st += n;
if(fz == ){
l = st-l+; r = st-r+;
if(l <= ) l += n; if(r <= ) r += n;
int ans = ;
if(l < r){
ans += get_ans(,l,);
ans += get_ans(r,n,);
if(t[].lft == t[].rgt) ans--;
}else ans += get_ans(r,l,);
printf("%d\n",ans);
}else{
l = st+l-; r = st+r-;
if(l > n) l -= n; if(r > n) r -= n;
int ans = ;
if(l > r){
ans += get_ans(,r,);
ans += get_ans(l,n,);
if(t[].lft == t[].rgt) ans--;
}else ans += get_ans(l,r,);
printf("%d\n",ans);
}
} void Paint(){
int l,r,xc; scanf("%d%d%d",&l,&r,&xc);
int st = (-rt); if(st <= ) st += n;
if(fz == ){
l = st-l+; r = st-r+;
if(l <= ) l += n; if(r <= ) r += n;
if(l < r){ Tpaint(,l,,xc); Tpaint(r,n,,xc);}
else Tpaint(r,l,,xc);
}else{
l = st+l-; r = st+r-;
if(l > n) l -= n; if(r > n) r -= n;
if(l > r){ Tpaint(,r,,xc); Tpaint(l,n,,xc);}
else Tpaint(l,r,,xc);
}
} void Swap(){
int l,r; scanf("%d%d",&l,&r);
int st = (-rt); if(st <= ) st += n;
if(fz == ){
l = st-l+; r = st-r+;
if(l <= ) l += n; if(r <= ) r+= n;
}else{
l = st+l-; r = st+r-;
if(l > n) l -= n; if(r > n) r -= n;
}
int nowl = get_color(l,),nowr = get_color(r,);
Tpaint(l,l,,nowr); Tpaint(r,r,,nowl);
} void work(){
int q; scanf("%d",&q);
for(int i=;i<=q;i++){
char ch = getchar();
while(ch > 'Z' || ch < 'A')ch = getchar();
switch(ch){
case 'R':{Rotate();break;}
case 'F':{fz ^= ;break;}
case 'S':{Swap();break;}
case 'P':{Paint();break;}
case 'C':{Count();break;}
}
}
} int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
read();
work();
return ;
}