OI Problems   关于

简化版

考虑后四种询问。

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

对于整个项链的查询，只需当成区间 [1,n][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);
    }
}

旋转与翻转

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

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

时间复杂度 Θ((N+Q)logN)\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][l,n] 和 [1,r][1,r] 两个部分计算，再合并即可。

  • 查询整个项链的颜色段数量时，要注意整个项链为同一种颜色的情况。（只需计算后答案与 11 取 max\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;
}