个人认为是一道非常赞的题目。

刚看到题目会感觉无从下手，因为颜色的情况太多太复杂了，这咋搞啊，这可做吗？翻到数据范围一栏，发现 $1 \le c_i \le 3$，这意味着总共只有 $1,2,3$ 三种颜色需要维护。

诶！这不就好做多了。那我们就可以暴力枚举所有 $6$ 种情况——哪种颜色最多，哪种颜色最少，哪种颜色中等。

设 $C_1$ 表示出现次数最多的颜色，$C_2$ 表示出现次数最少的颜色，$C_3$ 表示出现次数中等的颜色。

接着，就有一个结论：我们只需要考虑 $C_1$ 的出现次数与 $C_3$ 的出现次数之差恰好为 $k$ 的情况。不过当然你需要判断一下全局之差都不到 $k$ 的情况，这种时候直接输出 $n$ 就行。

啊，为什么？题目说的明明是 $\le k$ 呀！简单反证一下，假设我们找了一个最长的满足条件的区间，最大最小之差为 $d$ 且 $d < k$。那么只要此时区间不为 $[1,n]$（特判了），就一定能往某个方向扩展；而无论你怎么扩展，下一次的最大最小之差 $d' \le d+1 \le k$，也就是说扩展后的区间仍然满足条件，长度还比原先的多 $1$——与假设矛盾！所以我们只需要考虑差值恰好为 $k$ 的情况了，这大幅降低了难度。

在 $C_1,C_2,C_3$ 的假设基础上，我们定义前缀和数组 $s_1,s_2,s_3$ 分别表示三种颜色的前缀出现次数。那么区间 $[l,r]$ 满足题目条件当且仅当：

• $(s_{1,r} - s_{1,l-1}) \ge (s_{3,r} - s_{3,l-1})$
• $(s_{3,r} - s_{3,l-1}) \ge (s_{2,r} - s_{2,l-1})$
• $(s_{1,r} - s_{1,l-1}) - (s_{2,r} - s_{2,l-1}) = k$

做一个巧妙的换元：

• $a_i = s_{1,i} - s_{2,i}$
• $b_i = s_{1,i} - s_{3,i}$
• $c_i = s_{3,i} - s_{2,i}$

把换元后的 $a_i,b_i,c_i$ 代入前面的式子，移项后得到：

• $b_{l-1} \le b_r$
• $c_{l-1} \le c_r$
• $a_{l-1} + k = a_r$

感觉还是看不出什么？其实，现在已经可以做了。枚举 $a_{l-1}$，用桶存下所有可能的 $l-1$ 和 $r$，双指针维护即可，只是需要考虑 $b,c$ 两个参数都在范围内而已。好像是叫作三维数点。

好吧，这个我不会，三个参数怎么搞，好难，有没有别的更简单的方法？当然有！注意前面 $a_i,b_i,c_i$ 的定义，发现了吗，有一个很重要的性质——$a_i = b_i + c_i$！而 $a_r - a_{l-1} = k$，那么 $(b_r - b_{l-1}) + (c_r - c_{l-1}) = k$，也就是说，条件 $c_{l-1} \le c_r$ 完全可以被替换为 $b_l \ge k - b_r$。这样，原来的三个条件就被转化为：

• $b_r - k \le b_{l-1} \le b_r$
• $a_{l-1} + k = a_r$

$c$ 就这么没了。

那现在只剩两个参数了，二维数点还不简单吗？还是枚举 $a_{l-1}$ 的可能值，桶存下可能的 $l-1$ 和 $r$ 并双指针维护 $b_{l-1}$ 的情况即可，开个线段树，在下标 $b_{l-1}$ 处赋值 $l-1$，维护区间 $\min$ 值，就能在枚举到右端点时找到最小的合法 $l$ 啦！

不断更新答案，最后取最大即可。

线段树在每次做完后要还原，所以额外还有一个 $2$ 的常数。

时间复杂度 $O(C n \log n)$，其中 $C = 12$ 是一个常数。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 4e5+5;
const int INF = 0x3f3f3f3f;
int n,k,c[N],cnt[4];//桶
int ptmp[4];//用于排序多少
int s1[N],s2[N],s3[N];//前缀和数组
vector<int> pos[N];//用于记录对应数值下的下标
int tree[N<<2];//线段树开 4 倍空间
int Ans;//记录答案
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
int ls(int u){return (u<<1);}
int rs(int u){return (u<<1|1);}
void push_up(int u){
    tree[u]=min(tree[ls(u)],tree[rs(u)]);return;
}
void change(int u,int l,int r,int x,int k){
    if(l==r){tree[u]=k;return;}
    int mid=(l+r)>>1;
    if(x<=mid)change(ls(u),l,mid,x,k);
    else change(rs(u),mid+1,r,x,k);
    push_up(u);return;
}
int ask(int u,int l,int r,int L,int R){
    if(r<L||R<l)return INF;
    if(L<=l&&r<=R)return tree[u];
    int mid=(l+r)>>1,res=INF;
    res=min(res,ask(ls(u),l,mid,L,R));
    res=min(res,ask(rs(u),mid+1,r,L,R));
    return res;
}
//以上实现的是普通线段树
//单点修改，区间查询 min 值

void solve_(){//核心解决问题函数
    int C1=ptmp[1];//最大
    int C2=ptmp[2];//最小
    int C3=ptmp[3];//中间
    for(int i=0;i<=n;i++){
        if(i>=1){//i=0 是没有值的
            s1[i]=s1[i-1]+(c[i]==C1);
            s2[i]=s2[i-1]+(c[i]==C2);
            s3[i]=s3[i-1]+(c[i]==C3);
            //更新 i 这一位的前缀和数组
        }
        int nowa=s1[i]-s2[i];//定义的 a 数组
        pos[nowa+n].pb(i);
        //+n 是偏移量，怕出现负数
    }
    for(int xf=0;xf<=2*n;xf++){
        //枚举 a[l-1]=x
        int yf=xf+k;//表示 a[r]=y
        if(yf>2*n)break;//越界了
        vector<int> l=pos[xf];
        vector<int> r=pos[yf];
        //用两个临时数组存下左右端点的下标
        int lenl=l.size(),lenr=r.size();//存下长度
        int p1=0,p2=0;//双指针的两个指针下标
        while(p1<lenl||p2<lenr){//还没分配完
            //注意：如果下标相同，优先处理右端点
            //因为左端点本质上是左边一位，要求严格小于
            if(p2<lenr&&(p1==lenl||r[p2]<=l[p1])){
                //一定注意这里的判断！不能写成小于号！
                //此时处理的是右端点
                int id=r[p2],nowb=s1[id]-s3[id];
                //提取出当前位置的下标和 b 值
                int L=max(0,nowb-k+n),R=min(2*n,nowb+n);
                //提取可选的左端点的 b 值区间
                if(L<=R){//区间并非空集
                    int res=ask(1,0,2*n,L,R);//查询
                    if(res!=INF)Ans=max(Ans,id-res);//找到合法左端点，更新答案
                }
                p2++;//移动指针
            }else{
                //此时处理的是左端点
                int id=l[p1],nowb=s1[id]-s3[id];
                //提取出当前位置的下标和 b 值
                int yuan=ask(1,0,2*n,nowb+n,nowb+n);//原值
                if(yuan>id)change(1,0,2*n,nowb+n,id);
                //修改，注意为防止出现负数要偏移量
                p1++;//移动指针
            }
        }
        for(int x:l)change(1,0,2*n,s1[x]-s3[x]+n,INF);
        //还原线段树，把所有修改过的地方恢复至 INF
    }
    for(int i=0;i<=n;i++){
        int nowa=s1[i]-s2[i];//a 值
        pos[nowa+n].clear();//清空
    }
    return;
}
void DFS_perms(int u){
    if(u>3){solve_();return;}
    //排序结束，进入核心函数处理问题
    for(int i=1;i<=3;i++)if(!ptmp[i])//必须为空
        ptmp[i]=u,DFS_perms(u+1),ptmp[i]=0;//尝试后要清空
    return;//所有尝试都结束！
}
int main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++)
        cnt[c[i]=read()]++;//塞进桶
    memset(tree,0x3f,sizeof(tree));
    //给线段树全部赋值极值
    int minc=min({cnt[1],cnt[2],cnt[3]});
    int maxc=max({cnt[1],cnt[2],cnt[3]});
    //求出全局个数最大和最小
    if(maxc-minc<=k){cout<<n<<"\n";return 0;}
    //不用费心思匹配了，全局就是合法的
    DFS_perms(1);//DFS 找所有可行分配颜色方式
    cout<<Ans<<"\n";
    return 0;
}

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！