P15849 [NOISG 2026 Finals] 三只迅猛龙 / 3 Raptors 题解

· · 题解

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

刚看到题目会感觉无从下手，因为颜色的情况太多太复杂了，这咋搞啊，这可做吗？翻到数据范围一栏，发现 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] 满足题目条件当且仅当：

做一个巧妙的换元：

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

感觉还是看不出什么？其实，现在已经可以做了。枚举 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。这样，原来的三个条件就被转化为：

那现在只剩两个参数了，二维数点还不简单吗？还是枚举 $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](https://www.luogu.com.cn/record/281404536)] ```cpp #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; } ``` 如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！