#include<set>
#include<cstdio>
#include<iostream>
#define IT set<node>::iterator
using namespace std;
const int M=2e5+5;
inline int read(){ int x=0,f=1; char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} inline int cread(){ char c=getchar(); static int x;
	while(!isupper(c)) c=getchar();
	switch(c){
		case 'R': x=1; break;
		case 'F': x=2; break;
		case 'S': x=3; break;
		case 'P': x=4; break;
		case 'C': x=5; break;
	} c=getchar(); if(isupper(c)) x=6; return x;
} char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(int x,char chr='\n'){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]=chr;
}
inline void cmax(int& a,int b) { if(a<b) a=b; }
struct node { int l,r; mutable int v; //都是基操
	node(int l,int r=-1,int v=0):l(l),r(r),v(v){} node() {}
	bool operator < (const node& b) const { return l<b.l; }
}; set<node> s; IT it,lit,rit; int n,m,mov,rev;
inline IT split(int pos) { //都是基操
	it=s.lower_bound(node(pos));
	if(it!=s.end()&&it->l==pos) return it;
	--it; int l=it->l,r=it->r,v=it->v;
	s.erase(it),s.insert(node(l,pos-1,v));
	return s.insert(node(pos,r,v)).first;
}
inline void update(int l,int r,int v) { //都是基操
	rit=split(r+1),lit=split(l);
	s.erase(lit,rit),s.insert(node(l,r,v));
}
inline int query(int l,int r) { //人类的本质竟然是____
	int res=0,las=0;
	rit=split(r+1),lit=split(l);
	for(; lit!=rit; las=lit->v,++lit)
		res+=lit->v!=las;
	return res;
}
inline int col(int x) { //这里直接split
	return it=split(x),it->v;
}
inline int chg(int x) { //借(chao)来的
	if(rev) x=n-x+2;
	x-=mov;
	for(; x>n; x-=n);
	for(; x<1; x+=n);
	return x;
}
int main() {
	n=read(),m=read();
	for(int i=1,x; i<=n; ++i)
		x=read(),s.insert(node(i,i,x));
	int op,l,r,k,a,b,ans;
	for(int i=1,m=read(); i<=m; ++i) {
		op=cread();
		if(op==1) {
			k=read();
			mov+=(rev)?(-k):k;
			for(; mov>n; mov-=n);
			for(; mov<0; mov+=n);
		} else if(op==2) rev^=1;
		else if(op==3) {
			l=read(),r=read();
			l=chg(l),r=chg(r);
			a=col(l),b=col(r);
			update(l,l,b);
			update(r,r,a);
		} else if(op==4) {
			l=read(),r=read(),k=read();
			l=chg(l),r=chg(r);
			if(rev) swap(l,r);
			if(l<=r) update(l,r,k);
			else update(l,n,k),update(1,r,k);
		} else if(op==5) {
			ans=query(1,n);
			if(ans>1) ans-=col(1)==col(n); //这里要特判啊
			print(ans);
		} else if(op==6) {
			l=read(),r=read();
			l=chg(l),r=chg(r);
			if(rev) swap(l,r);
			if(l<=r) ans=query(l,r);
			else {
				ans=query(l,n)+query(1,r);
				if(ans>1) ans-=col(1)==col(n); //这里也是
			}
			print(ans);
		}
	} return Ot(),0;
}

简化版

考虑后四种询问。

把整个项链当成一条链来做，在其上建线段树，维护不同颜色的段数。合并时还需要用到区间两端的颜色，所以对每个区间还需要维护区间两端颜色。

对于整个项链的查询，只需当成区间 $[1,n]$ 来做，在特判两端是否为同种颜色即可。

namespace SegmentTree{
    struct Node{
        int left,right,cnt; // 最左/右的颜色 / 不同颜色数量
        int tag;
    }a[1000001];
    void pushup(int id){
        int l=id<<1,r=(id<<1)+1;
        a[id].left=a[l].left,
        a[id].right=a[r].right;
        a[id].cnt=a[l].cnt+a[r].cnt;
        if(a[l].right==a[r].left)a[id].cnt--;
    }
    void pushdown(int id){
        int l=id<<1,r=(id<<1)+1;
        if(a[id].tag==0)return;
        a[l].left=a[l].right=a[l].tag=a[id].tag;
        a[r].left=a[r].right=a[r].tag=a[id].tag;
        a[l].cnt=a[r].cnt=1,a[id].tag=0;
    }

    void build(int id,int l,int r){
        if(l==r){
            a[id].left=a[id].right=x[l],a[id].cnt=1;
            return;
        }
        int mid=l+r>>1;
        build(id<<1,l,mid);
        build((id<<1)+1,mid+1,r);
        pushup(id);
    }
    Node query(int id,int l,int r,int L,int R){
        if(L<=l&&r<=R)return a[id];
        int mid=l+r>>1;
        pushdown(id);
        Node lNode={0,0,0,0},rNode={0,0,0,0};
        if(L<=mid)lNode=query(id<<1,l,mid,L,R);
        if(R>mid) rNode=query((id<<1)+1,mid+1,r,L,R);
        return {
            lNode.left==0?rNode.left:lNode.left,
            rNode.right==0?lNode.right:rNode.right,
            lNode.cnt+rNode.cnt-(lNode.right==rNode.left?1:0),
            0
        };
    }
    void update(int id,int l,int r,int L,int R,int color){
        if(L<=l&&r<=R){
            a[id].left=a[id].right=a[id].tag=color,a[id].cnt=1;
            return;
        }
        int mid=l+r>>1;
        pushdown(id);
        if(L<=mid)update(id<<1,l,mid,L,R,color);
        if(R>mid) update((id<<1)+1,mid+1,r,L,R,color);
        pushup(id);
    }
}

旋转与翻转

下面考虑旋转和对称怎么做。

容易想到只需考虑将询问反向旋转即可。用 $flipped$ 表示是否翻转过，$rotated$ 表示旋转的个数。只需对于输入的每个位置都反向转换即可。

时间复杂度 $\Theta((N+Q)\log N)$。

bool flipped; int rotated;
void convert(int &x){
    if(flipped)x=rotated+2-x;
    else x-=rotated;
    x=(x+n+n-1)%n+1;
}

实现细节

本题细节较多，码量较大。 实现细节：

• 查询区间颜色段数量时，需要注意输入的区间两端是按顺时针方向的，而不是从编号小的到编号大的。若编号大的在前，只需将区间拆为 $[l,n]$ 和 $[1,r]$ 两个部分计算，再合并即可。

• 查询整个项链的颜色段数量时，要注意整个项链为同一种颜色的情况。（只需计算后答案与 $1$ 取 $\max$ 即可。）

// 2023.05.24

#include<bits/stdc++.h>
using namespace std;

int n,c,q,x[500001];

namespace SegmentTree{
    struct Node{
        int left,right,cnt; // 最左/右的颜色 / 不同颜色数量
        int tag;
    }a[1000001];
    void pushup(int id){
        int l=id<<1,r=(id<<1)+1;
        a[id].left=a[l].left,
        a[id].right=a[r].right;
        a[id].cnt=a[l].cnt+a[r].cnt;
        if(a[l].right==a[r].left)a[id].cnt--;
    }
    void pushdown(int id){
        int l=id<<1,r=(id<<1)+1;
        if(a[id].tag==0)return;
        a[l].left=a[l].right=a[l].tag=a[id].tag;
        a[r].left=a[r].right=a[r].tag=a[id].tag;
        a[l].cnt=a[r].cnt=1,a[id].tag=0;
    }

    void build(int id,int l,int r){
        if(l==r){
            a[id].left=a[id].right=x[l],a[id].cnt=1;
            return;
        }
        int mid=l+r>>1;
        build(id<<1,l,mid);
        build((id<<1)+1,mid+1,r);
        pushup(id);
    }
    Node query(int id,int l,int r,int L,int R){
        if(L<=l&&r<=R)return a[id];
        int mid=l+r>>1;
        pushdown(id);
        Node lNode={0,0,0,0},rNode={0,0,0,0};
        if(L<=mid)lNode=query(id<<1,l,mid,L,R);
        if(R>mid) rNode=query((id<<1)+1,mid+1,r,L,R);
        return {
            lNode.left==0?rNode.left:lNode.left,
            rNode.right==0?lNode.right:rNode.right,
            lNode.cnt+rNode.cnt-(lNode.right==rNode.left?1:0),
            0
        };
    }
    void update(int id,int l,int r,int L,int R,int color){
        if(L<=l&&r<=R){
            a[id].left=a[id].right=a[id].tag=color,a[id].cnt=1;
            return;
        }
        int mid=l+r>>1;
        pushdown(id);
        if(L<=mid)update(id<<1,l,mid,L,R,color);
        if(R>mid) update((id<<1)+1,mid+1,r,L,R,color);
        pushup(id);
    }
}

bool flipped; int rotated;
void convert(int &x){
    if(flipped)x=rotated+2-x;
    else x-=rotated;
    x=(x+n+n-1)%n+1;
}

int main(){
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
        scanf("%d",x+i);
    SegmentTree::build(1,1,n);
    scanf("%d",&q);
    while(q--){
        string op; cin>>op;
        if(op=="R"){
            // 顺时针旋转 k 位
            int k; scanf("%d",&k);
            rotated=(rotated+k)%n;
        }
        if(op=="F"){
            // 沿给定对称轴翻转
            flipped=!flipped,
            rotated=(n-rotated)%n;
        }
        if(op=="S"){
            // 交换两个珠子
            int i,j;
            scanf("%d%d",&i,&j);
            convert(i),convert(j);
            int color1=SegmentTree::query(1,1,n,i,i).left;
            int color2=SegmentTree::query(1,1,n,j,j).left;
            if(color1!=color2)
                SegmentTree::update(1,1,n,i,i,color2),
                SegmentTree::update(1,1,n,j,j,color1);
        }
        if(op=="P"){
            // 将 i 顺时针方向到 j 的一段染为 x
            int i,j,x;
            scanf("%d%d%d",&i,&j,&x);
            convert(i),convert(j);
            if(flipped)swap(i,j);
            if(i<=j)SegmentTree::update(1,1,n,i,j,x);
            else
                SegmentTree::update(1,1,n,i,n,x),
                SegmentTree::update(1,1,n,1,j,x);
        }
        if(op=="C"){
            // 查询当前项链有多少个部分组成
            printf("%d\n",max(SegmentTree::a[1].cnt-
                (SegmentTree::a[1].left==SegmentTree::a[1].right),1));
        }
        if(op=="CS"){
            // 查询从 i 顺时针方向到 j 有多少个部分组成
            int i,j;
            scanf("%d%d",&i,&j);
            convert(i),convert(j);
            if(flipped)swap(i,j);
            int res=0;
            if(i<=j)
                printf("%d\n",SegmentTree::query(1,1,n,i,j).cnt);
            else printf("%d\n",SegmentTree::query(1,1,n,i,n).cnt
                +SegmentTree::query(1,1,n,1,j).cnt
                -(SegmentTree::a[1].left==SegmentTree::a[1].right));
        }
    }
    return 0;
}