#C220816C. 时间复杂度
C220816C 校内模拟赛
背景
注意：本题采用捆绑测试。
题目描述
在你的帮助下，小凯成功找到了宝藏价值最大的方案。接下来他在闲逛时被一个游戏机吸引了。
游戏机中共有 \(n\) 个带颜色的小球，第 \(i\) 个小球的颜色是 \(a_i\) 。小凯需要选出一个区间（假设长度为 \(l\) ），满足对于任意颜色的小球：
- 要么在这个区间中出现 \(0\) 次（即不出现）；
- 要么在这个区间中出现次数 \(≥b_l\) 。
其中 \(b_l\) 是一个给定的数组，且满足对于任意 \(i<j\) 有 \(b_i≥b_j\) 。如果最终小凯选出的区间越长，获得的奖励就越大。
小凯想用 OI 知识解决这个问题，但是由于水平问题，他只会 \(O(n^3)\)，而游戏机中的球非常多。因此他又来厚颜无耻地找你，希望你能帮他优化时间复杂度，解决这个问题。
即求出，最长满足要求的区间长度是多少。特别的，若问题无解，输出 \(0\) 。
输入格式
第一行共一个数 \(n\) 。
第二行共 \(n\) 个数字，表示 \(a_i\)。
第三行共 \(n\) 个数字，表示 \(b_i\) 。
输出格式
输出共一个数字，表示最长的合法区间长度。
样例
输入数据 1
7
2 0 4 0 4 3 2
3 3 3 2 2 2 2
输出数据 1
4
样例说明
选 \(0\) \(4\) \(0\) \(4\) 显然最优。
数据规模与约定
subtask1(10pts) ：n≤300。
subtask2(15pts) ：n≤1500。
subtask3(20pts) ：n≤100000。
subtask4(20pts) ：保证所有 \(b_i\) 都相等。
subtask5(35pts) ：无特殊限制。
对于 \(100%\) 的数据，\(n≤10^6；0≤a_i≤n；1≤b_i≤n+1\)，且满足对于任意 \(i<j\) 有 \(b_i≥b_j\)。
Tips： 由于输入输出量较大，建议使用快速输入输出。
Solution
题目中有一个及其重要的条件，就是 \(b\) 数组是不严格递减的，同时长度是在单调上升的，所以就会有一个发现：小区间的限制比大区间的限制更多。
假如有一个区间 \([l,r]\) 包含 \(pos\)，并且这个区间只有 \(pos\) 的数量是小于 \(b[r-l+1]\) 的，那么会发现因为小区间的 \(b\) 值只会比大区间更大，而 \(pos\) 的数量只会比大区间的少，所以如果大区间因为 \(pos\) 的数量太少而无法成为合法区间，那么这个大区间内所有包含 \(pos\) 的小区间也不会是合法的。根据这点就诞生了这一种做法。
将原序列作为一个大区间，然后在这个大区间中找到所有导致这个大区间不合法的 \(pos\) 值，并依照这些 \(pos\) 值将大区间拆成很多小区间，递归处理，如果找不到这样的 \(pos\)，那么当前的区间就是一个合法区间，可以用来更新答案。
用样例来解释，第一轮：
\[\begin{matrix} 2&0&4 &0 &4 &3 &2\\ &&&&&\uparrow \end{matrix} \]划分成为：
\[\begin{matrix} (2&0&4&0&4)&\square&(2) \end{matrix} \]这两个区间，然后递归进入这两个区间（右侧那个单 \(2\) 的显然是不可能，所以就不继续往下画图了）。
\[\begin{matrix} 2&0&4&0&4\\ \uparrow \end{matrix} \]划分成为：
\[\begin{matrix} \square&(0&4&0&4) \end{matrix} \]再次递归进入新的小区间，发现是一个合法的区间，更新答案。
可以得知每个数出现次数总共有 \(\sqrt{n}\) 种情况，所以可以得知这种做法的时间复杂度是 \(\mathcal O(n\sqrt n)\) 的，可以通过 subtask3，但无法通过 subtask5。
考虑怎么优化这种做法。不难发现可以将一次找完大区间内所有的 \(pos\) 值这一步带来了巨大的时间开销，这一步可以被替换为找到大区间中的任意一个 \(pos\) 值来对大区间进行分割，这样的正确性是可以保证的，并且相比之前那种做法还更易实现。
为了使找 \(pos\) 的过程耗时尽可能少，我们最好要选到最靠近大区间端点的 \(pos\) 值，然后以这个 \(pos\) 值来分割区间。但是因为我们不知道这个 \(pos\) 到底靠哪一边，所以最坏的情况下仍然会是 \(\mathcal O(n)\) 的。这时候有一种比较神奇的做法，类似于 \(\texttt{meet in the middle}\)，是在当前大区间的左右端点都整一个指针同时向中间移动，这样最坏情况下也只会跑一半区间的长度。到了这里，我们已经将大区间按照 \(pos\) 分割成为了一个小区间和另一个稍大的区间（这个稍大的区间之后就称为大区间了）。这时，有一种类似 \(\texttt{dsu on tree}\) 的启发式合并思想，先将小的区间清除对答案的贡献，然后计算大区间的贡献并保留，再计算小区间的贡献并且保留对答案的影响（与 \(\texttt{dsu on tree}\) 的基本思想一致）。不难发现，这种情况下最坏的分治树也只会变成线段树的样子，所以时间复杂度就是启发式合并的 \(\mathcal O(n\log n)\)。
Code
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
void read(auto &k)
{
k=0;auto flag=1;char b=getchar();
while (!isdigit(b)) {flag=(b=='-')?-1:1;b=getchar();}
while (isdigit(b)) {k=k*10+b-48;b=getchar();}
k*=flag;
}
void write(auto x) {if (x<0) {putchar('-');write(-x);return;}if (x>9) write(x/10);putchar(x%10+'0');}
void writewith(auto x,char c) {write(x);putchar(c);}
const int _SIZE=1e6;
int n,a[_SIZE+5],b[_SIZE+5];
int cnt[_SIZE+5],res;//cnt是桶，res记录答案
void calc(int l,int r)
{
if (r<l || r-l+1<=res)//如果区间非法或者是比答案小，那么直接清除贡献
{
for (int i=l;i<=r;i++) --cnt[a[i]];
return;
}
if (l==r)//单点，更新答案后清除贡献
{
--cnt[a[l]];
if (b[1]==1) res=max(res,1);
return;
}
int p=l,q=r,pos=-1,target=b[r-l+1];
while (p<=q)//双指针寻找pos值
{
if (cnt[a[p]]<target) {pos=p;break;}
if (cnt[a[q]]<target) {pos=q;break;}
q--,p++;
}
if (pos<0)//不存在pos值
{
res=max(res,r-l+1);//更新答案
for (int i=l;i<=r;i++) --cnt[a[i]];//清除贡献
return;
}
if (pos<=((l+r)>>1))//pos靠左，左侧为小区间
{
for (int i=l;i<=pos;i++) --cnt[a[i]];//清除左侧小区间贡献
calc(pos+1,r);//计算右侧贡献
for (int i=l;i<pos;i++) ++cnt[a[i]];//计算左侧贡献
calc(l,pos-1);
}
else
{
for (int i=pos;i<=r;i++) --cnt[a[i]];//同上
calc(l,pos-1);
for (int i=pos+1;i<=r;i++) ++cnt[a[i]];
calc(pos+1,r);
}
}
signed main()
{
read(n);
for (int i=1;i<=n;i++) read(a[i]),cnt[a[i]]++;
for (int i=1;i<=n;i++) read(b[i]);
calc(1,n);//原序列直接作为大区间
writewith(res,'\n');
return 0;
}