大致题意
给一个串包含(n)个珠子的项链,其中第(i)个珠子的颜色是(c_i)
现在要求维护以下几个操作:
(n,m≤500000)
分析
细节巨多的一道线段树题
调了将近四个小时/kk
如果没有翻转操作,这就是个线段树裸题
不难发现,翻转操作只是把顺时针旋转变成了逆时针旋转
维护两个变量(r)和(k),分别代表旋转的幅度和是否翻转,然后就可以通过计算轻松搞出查询区间了
亿点细节
-
区间颜色全部相同时要特判
-
旋转后区间要翻转
-
注意题目中给的是一个环,因此要特判(l≤r)和(l＞r)的情况
-
区间赋值相加tag,傻逼!
-
交换操作用原数列数据,傻逼!
using namespace std;
const int MAXN = 500010;
#define lson node<<1
#define rson node<<1|1
inline int read(){
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
int n,m,a[MAXN];
int now;
int T[MAXN];
int cnt = 0;
bool is_rotate;
struct st{
int l,r,val,tag;
}tree[MAXN<<2];
stack<st> s;
void pushdown(int node){
if(!tree[node].tag) return;
tree[lson].l = tree[lson].r = tree[rson].l = tree[rson].r = tree[node].tag;
tree[lson].tag = tree[node].tag;
tree[rson].tag = tree[node].tag;
tree[lson].val = tree[rson].val = 1;
tree[node].tag = 0;
}
void pushup(int node){
tree[node].l = tree[lson].l;
tree[node].r = tree[rson].r;
if(tree[lson].r == tree[rson].l){
tree[node].val = tree[lson].val+tree[rson].val -1;
}
else tree[node].val = tree[lson].val+tree[rson].val;
}
void build(int node,int l,int r){
if(l==r){
tree[node].l = tree[node].r = a[l];
tree[node].val = 1;
return;
}
int mid = (l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(node);
}
int query(int node,int l,int r,int x,int y){
if(x<=l&&y>=r){
return tree[node].val;
}
pushdown(node);
int mid = (l+r)>>1;
if(x<=mid&&y>mid) return query(lson,l,mid,x,y)+query(rson,mid+1,r,x,y)-(tree[lson].r==tree[rson].l);
if(x<=mid) return query(lson,l,mid,x,y);
if(y>mid) return query(rson,mid+1,r,x,y);
pushup(node);
}
st find(int node,int l,int r,int x,int y){
if(x<=l&&y>=r){
return tree[node];
}
pushdown(node);
int mid = (l+r)>>1;
if(x<=mid) return find(lson,l,mid,x,y);
if(y>mid) return find(rson,mid+1,r,x,y);
}
/*int merge2(){
int ans = 0;
st last;
while(!s.empty()){
st a = s.top();
s.pop();
ans+=a.val;
if(a.l==last.r) ans--;
last = a;
//cout<<"["<<a.l<<" "<<a.r<<"]"<<" "<<a.val<<" ";
}
return ans;
}*/
void modify(int node,int l,int r,int x,int y,int val){
if(x<=l&&y>=r){
tree[node].val = 1;
tree[node].tag = val;
tree[node].l = tree[node].r = val;
return;
}
pushdown(node);
int mid = (l+r)>>1;
if(x<=mid) modify(lson,l,mid,x,y,val);
if(y>mid) modify(rson,mid+1,r,x,y,val);
pushup(node);
}
void calc(int &x,int &y){
if(!is_rotate)
{
if(x>=now+1)x=x-now;
else x=n-now+x;
if(y>=now+1) y=y-now;
else y=n-now+y;
}else
{
if(x<=now+1)x=now-x+2;
else x=now+n-x+2;
if(y<=now+1) y=now-y+2;
else y=now+n-y+2;
}
}
int main(){
n = read(),m = read();
for(int i=1;i<=n;i++) a[i] = read();
build(1,1,n);
int t;
t = read();
while(t--){
char opt[2];
cin>>opt;
if(opt[0]=='R'){
int k = read();
now = (now+k)%n;
}
else if(opt[0]=='F'){
is_rotate = !is_rotate;
now = (n-now)%n;
}
else if(opt[0]=='P'){
int l = read(),r = read(),val = read();
calc(l,r);
if(is_rotate) swap(l,r);
if(l<=r) modify(1,1,n,l,r,val);
else modify(1,1,n,l,n,val),modify(1,1,n,1,r,val);
}
else if(opt[0]=='C'&&opt[1]!='S'){
if(tree[1].l!=tree[1].r) cout<<tree[1].val<<endl;//T[++cnt] = tree[1].val;
else cout<<max(1,tree[1].val - 1)<<endl;//T[++cnt] = tree[1].val-1;
}
else if(opt[0]=='S'){
int l =read(),r = read();
calc(l,r);
st a = find(1,1,n,l,l);
st b = find(1,1,n,r,r);
modify(1,1,n,l,l,b.l);
modify(1,1,n,r,r,a.l);
}
else{
int l = read(),r = read();
calc(l,r);
if(is_rotate) swap(l,r);
//cout<<"["<<l<<" "<<r<<"]"<<endl;
if(l<=r) cout<<query(1,1,n,l,r)<<endl;
else{
cout<<max(1,query(1,1,n,l,n)+query(1,1,n,1,r)-(tree[1].l==tree[1].r))<<endl;
}
// T[++cnt] = merge();
}
}
}