题目

https://www.luogu.org/problemnew/show/P4130

---

解题思路

$Splay不会$，那就正经的打线段树。
这道题目的后4问，就是纯正的线段树。
对于前两问，其实只是改变了每一个端点的位置，但没有改变他们的顺序，所以我们可以记录下他们的翻转次数和旋转次数，查询时倒推回去就可以了。
细节很多。

比如打函数名的时候，注意$swap$是常用库中的定义函数，尽量不要重复。

---

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
using namespace std; 
const int N=500010; 
int n,m,flag,Q,sum,b[N]; char ch[5]; 
struct node{int l,r,lv,rv,cn,la; 
}a[N*4];
inline int read(){int p=0; char c=getchar(); while (!isdigit(c)) c=getchar(); while (isdigit(c)) p=p*10+c-48,c=getchar(); return p; 
}
void up(int x){a[x].cn=a[x*2].cn+a[x*2+1].cn; if (a[x*2].rv==a[x*2+1].lv) a[x].cn--; a[x].lv=a[x*2].lv,a[x].rv=a[x*2+1].rv; 
}
void pushlazy(int x){if (a[x].la){a[x*2].lv=a[x*2].rv=a[x*2].la=a[x].la; a[x*2+1].lv=a[x*2+1].rv=a[x*2+1].la=a[x].la; a[x*2].cn=a[x*2+1].cn=1; a[x].la=0; }
}
void build(int x){if (a[x].l==a[x].r){a[x].lv=a[x].rv=b[a[x].l]; a[x].cn=1; return; }int mid=(a[x].l+a[x].r)>>1; a[x*2].l=a[x].l,a[x*2].r=mid;a[x*2+1].l=mid+1,a[x*2+1].r=a[x].r; build(x*2),build(x*2+1); up(x); 
}
int find(int x,int k){if (a[x].l==a[x].r) return a[x].lv; pushlazy(x); int mid=(a[x].l+a[x].r)>>1; if (k<=mid) find(x*2,k); else find(x*2+1,k); 
}
void change(int x,int k,int val){if (a[x].l==k&&a[x].r==k){a[x].lv=a[x].rv=val; a[x].cn=1; return; }pushlazy(x); int mid=(a[x].l+a[x].r)>>1; if (k<=mid) change(x*2,k,val); else change(x*2+1,k,val); up(x); 
}
void changes(int x,int l,int r,int val){if (a[x].l==l&&a[x].r==r) {a[x].lv=a[x].rv=a[x].la=val; a[x].cn=1; return; }if (a[x].l==a[x].r) return; pushlazy(x); int mid=(a[x].l+a[x].r)>>1; if (r<=mid) changes(x*2,l,r,val); else if (l>mid) changes(x*2+1,l,r,val); else changes(x*2,l,mid,val),changes(x*2+1,mid+1,r,val); up(x); 
}
void Swap(int x,int y){int qx=find(1,x),qy=find(1,y); change(1,y,qx),change(1,x,qy);
}
int ask(int x,int l,int r){if (a[x].l==l&&a[x].r==r) return a[x].cn; pushlazy(x); int mid=(a[x].l+a[x].r)>>1; if (r<=mid) return ask(x*2,l,r); if (l>mid) return ask(x*2+1,l,r); int ans=ask(x*2,l,mid)+ask(x*2+1,mid+1,r); if (a[x*2].rv==a[x*2+1].lv) ans--; return ans; 
}
int get(){int x=read();if (flag) x=n-x+2; return ((x-sum)%n+2*n-1)%n+1;
}
int main(){
//	freopen("testdata.in","r",stdin); n=read(),m=read(); rep(i,1,n) b[i]=read(); a[1].l=1,a[1].r=n; build(1); Q=read(); int x,y,k; while (Q--){scanf("%s",ch); if (ch[0]=='R') {k=read(); if (flag) sum-=k; else sum+=k; }if (ch[0]=='F') flag^=1; if (ch[0]=='S') {x=get(),y=get(); Swap(x,y); }if (ch[0]=='P') {x=get(),y=get(),k=read(); if (flag) swap(x,y); if (x<=y) changes(1,x,y,k); else changes(1,1,y,k),changes(1,x,n,k); }if (ch[0]=='C'&&ch[1]=='S'){x=get(),y=get(); if (flag) swap(x,y); if (x<=y) printf("%d\n",ask(1,x,y)); else {int ans=ask(1,1,y)+ask(1,x,n); if (a[1].lv==a[1].rv) ans--; printf("%d\n",ans); }}if (ch[0]=='C' && ch[1]!='S'){int ans=ask(1,1,n);if (a[1].lv==a[1].rv&&ans!=1) ans--;printf("%d\n",ans); }}
}