前言

这题怎么被邪恶出题人加强到多次询问子区间扔模拟赛里面了？

加强后需要两个结论，而本题任取一个即可。赛时只搓出来一个还写挂了，遗憾离场。

对于 $q$ 次查询子区间 $[l,r]$，有任意一个结论就可以 $O(nq)$，两个结论可以 $O(n+q)$。

结论一

赛时搓出来的。给定一个左端点 $l$，限制 $r\le R$，我们在恰当的预处理后可以 $O(1)$ 求出最大的合法的 $r$。下面应用左闭右开区间 $[l,r)$，这样方便实现。

对于当前的 $[l,r)$，不妨令三种颜色出现次数 $a\le b\le c$，若 $a<b<c$ 则直接结束。

特别注意，下面的操作中，$a,b,c$ 的书写都有 $a\le b\le c$，可能在某次变换后，成为 $a\le c\le b$，则会调换隐式顺序，依然认为是 $a\le b\le c$。同时，会为了方便，将 $a,b,c$ 和对应颜色混用的情况。

先预处理一个 $pre_{i,c}$ 表示 $[1,i)$ 中最大的颜色不是 $c$ 的下标，显然 $O(n)$。

然后开始大力分讨，分为四种情况：$a=b=c,a=b<c,a+1=b=c,a+1<b=c$。

• 对于 $a+1=b=c$，右端点 $-1$ 则可以转化为 $a+1<b=c$ 或 $a=b<c$，转化是 $O(1)$ 的。

• 对于 $a+1<b=c$，跳到 $pre_{r,a}$ 即可让 $b,c$ 中某一个 $-1$ 从而不等，也是 $O(1)$，也不会漏解。

• 对于 $a=b<c$，右端点 $-1$ 后可能是 $a=b<c$ 或 $a=b=c$ 或 $a<b<c$。

• 对于 $a=b=c$，右端点 $-1$ 后是 $a+1=b=c$。

发现上述情况中可能出现环，这样就无法保证是 $O(1)$ 的了。

考虑在 $a=b=c$ 时把环强制断掉，用辅助数组 $jmp$ 来完成，对于 $jmp_i$，若 $i-1,i-2,i-3$ 颜色有相同，则 $jmp_{i}=i-1$ 表示普通左移；否则设为 $jmp_{i-3}$ 用来快速跳过。

那么，到达状态 $a=b=c$ 后，跳跃一次 $jmp$ 成为 $a+1=b=c$ 后，只用两种可能：右端点 $-1$ 得到 $a+1<b=c$；右端点 $-1$ 得到 $a=b<c$ 后再 $-1$ 得到 $a<b<c$，否则应当被 $jmp$ 跳过。

总结一下实现：

• 对于 $a+1<b=c$，跳到 $pre_{r,a}$。

• 对于 $a+1=b=c$，跳 $pre_{r,a}$ 即可，若最后一个不是 $a$ 对应颜色，则会转移到 $a=b<c$。

• 对于 $a=b=c$，跳 $jmp_r$ 后 $O(1)$ 步即可结束。

• 对于 $a=b<c$，能否直接跳到 $pre_{r,c}$？并不能，直接跳可能让我们错失 $a=b=c$ 的位置，从而陷入大量的循环，应该跳到 $\max(pre_{r,c},r-cnt_c+cnt_a)$，这样就到达 $a=b=c$ 或 $a<b<c$。

如何构造 hack 跳 $pre_{r,c}$ 的数据？考虑序列：$(abccba)^ka$ 即可。

:::info[据此实现的代码]

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

const int N=1000005;
int n,res,C[3],B[N];
char str[N];

inline int pmax(int a,int b){return a>b?a:b;}
inline void cmax(int &a,int b){(a<b)&&(a=b);}

class work{
    private://pre 记录前一个不同的位置，jmp 用来跳过 （123）这种段状物
    int A[N],pre[N][3],jmp[N],lst[4],sum[N][3];
    inline void calccnt(int l,int r){
        C[0]=sum[r][0]-sum[l-1][0];
        C[1]=sum[r][1]-sum[l-1][1];
        C[2]=sum[r][2]-sum[l-1][2];
    }
    public:
    inline int calc(int l,int r){//传入的 r 闭区间
        static int a,b,c;
        r++,calccnt(l,r-1);
        for(;(C[0]==C[1]||C[1]==C[2]||C[2]==C[0])&&r>l;){
            if(C[0]==C[1]&&C[1]==C[2]) r=jmp[r];
            else{
                if(C[0]==C[1]) a=0,b=1,c=2;
                if(C[0]==C[2]) a=0,b=2,c=1;
                if(C[1]==C[2]) a=1,b=2,c=0;
                if(C[a]<C[c]) r=pmax(r-C[c]+C[a],pre[r][c]);
                else r=pre[r][c];//跳到首个不为 c 的位置
            }
            calccnt(l,r-1);
        }
        return r-l;
    }
    inline void init(){
        lst[0]=lst[1]=lst[2]=0,jmp[1]=0,jmp[2]=1,jmp[3]=2;
        sum[0][0]=sum[0][1]=sum[0][2]=0;
        for(int i=1;i<=n;i++) A[i]=B[i];
        for(int i=1;i<=n+1;i++){
            lst[A[i-1]]=i-1;
            pre[i][0]=pmax(lst[1],lst[2]),sum[i][0]=sum[i-1][0]+(A[i]==0);
            pre[i][1]=pmax(lst[0],lst[2]),sum[i][1]=sum[i-1][1]+(A[i]==1);
            pre[i][2]=pmax(lst[0],lst[1]),sum[i][2]=sum[i-1][2]+(A[i]==2);
        }
        for(int i=4;i<=n+1;i++) jmp[i]=(A[i-1]^A[i-2]^A[i-3])==3?jmp[i-3]:i-1;
    }
}T;

int main(){
    scanf("%d %s",&n,str+1);
    for(int i=1;i<=n;i++){
        if(str[i]=='B') B[i]=0;
        if(str[i]=='S') B[i]=1;
        if(str[i]=='C') B[i]=2;
    }
    T.init();
    for(int i=1;i<=n;i++) cmax(res,T.calc(i,n));
    if(res==0) puts("NIE");
    else cout<<res;
    return 0;
}

:::

代码很容易假掉，但数据未必能卡掉，可以拍个几千组小数据自测一下。也欢迎 hack 我的代码。

结论二

一定存在一个最优解 $[l,r]$，使得 $\min(n-r+1,l)\le 3$。序列长度不足的直接判掉。只需证明：对于一个合法解，若左右各有三个字符，则一定能得到包含它的更优解。

这显然可以大分讨证明，但我们有计算机！考虑写个爆搜验证一下。

同样设 $a<b<c$，这里不妨令 $a=0$，由于两侧只增加六个数，过大的差距是不必要的，这里可以令 $b\le 7,c\le b+7$。区区几万的枚举量简直太轻松了！

:::info[搜索验证程序]

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

int A[10],cnt;
//a->0，b->1，c->2
void dfs(int p,int b,int c){
    if(p==6){
        int flag=0;
        for(int l=0;l<=3;l++){for(int r=2;r<=5;r++){
            if(l==3&&r==2) continue;//没有扩展
            int a[3]={0,b,c};
            if(l<=2) a[A[2]]++;
            if(l<=1) a[A[1]]++;
            if(l<=0) a[A[0]]++;
            if(r>=3) a[A[3]]++;
            if(r>=4) a[A[4]]++;
            if(r>=5) a[A[5]]++;
            if(a[0]!=a[1]&&a[1]!=a[2]&&a[2]!=a[0]) flag=1;
        }}
        assert(flag==1),cnt++;return;
    }//这里大概有 7*7*(3^6) 种方案，不建议输出查看
    for(int i=0;i<=2;i++) A[p]=i,dfs(p+1,b,c);
}

int main(){
    for(int b=1;b<=7;b++){for(int c=b+1;c<=b+7;c++) dfs(0,b,c);}
    cout<<cnt;//检验一下 35721
    return 0;
}

:::

代码就不额外贴了，前面已经有了一份。