题解：CF786C Till I Collapse
ARIS2_0
·
·
题解
前言
实际上本题的根号分治可以不使用二分，以达到 O(n\sqrt{n}) 的复杂度。
思路
不难发现，分组的组数不会超过 $\lceil\frac{n}{k}\rceil$，考虑根号分治。
记 $B=\lceil{\sqrt{n}}\rceil$。
我们对于 $k\le B$ 的 $k$，直接暴力计算答案，时间复杂度 $O(n\sqrt{n})$；
对于 $k>B$ 的 $k$，由于其分组组数不超过 $B$，我们**记录每一组的右端点**，更新时只需要**将这 $B$ 个右端点尽量向右移，直到无法移动**即可。
右端点最多只会移动 $O(n\sqrt{n})$ 次，遍历的复杂度也是 $O(n\sqrt{n})$ 的，总时间复杂度为 $O(n\sqrt{n})$。
### 实现细节
实现上，我们开 $B$ 个桶，第 $i$ 个桶记录第 $i$ 块的信息。当我们移动第 $i$ 块的右端点时，我们去更新第 $i$ 块和第 $i+1$ 块的桶（移动第 $i$ 块的右端点的同时也移动了第 $i+1$ 块的左端点），同时判断能否继续向右移。
当遇到一个块的右端点移到了 $n$ 时，说明答案就是这个块的编号，直接输出即可。
### Code
```cpp
#include<bits/stdc++.h>
using namespace std;
constexpr int maxn=1e5+10,maxs=330;
int n,a[maxn],B,cnt[maxn],z[maxn],cz[maxs][maxn],ans[maxs];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
B=ceil(sqrtl(n));
int tot=0;
//这个循环是暴力，同时用 z 记录分界点
for(int i=1;i<=B;i++){
int last=1,res=0;
tot=0;
for(int j=1;j<=n;j++){
if(cnt[a[j]]==0 and res+1>i){
z[++tot]=j-1;
for(int k=last;k<j;k++)cnt[a[k]]--;
last=j;
res=0;
}
if(cnt[a[j]]==0)res++;
cnt[a[j]]++;
}
z[++tot]=n;
for(int k=last;k<=n;k++)cnt[a[k]]--;
cout<<tot<<" ";
}
//预处理 ans[i]（第 i 块中数字的种类数）和 cz[i]（对第 i 块开的桶）
for(int i=1;i<=tot;i++){
for(int j=z[i-1]+1;j<=z[i];j++){
if(cz[i][a[j]]==0)ans[i]++;
cz[i][a[j]]++;
}
}
for(int i=B+1;i<=n;i++){
int eans=0;
for(int j=1;j<=tot;j++){
//这里是有可能出现 z[j]<z[j-1] 的情况的，但是不会影响到答案统计。
//因为在 z[j]<z[j-1] 时，ans[j] 永远为 0，cz[j] 这个桶随着 z[j] 变大也会自动还原。
while(z[j]<n and ans[j]+(cz[j][a[z[j]+1]]==0)<=i){
z[j]++;
ans[j]+=(cz[j][a[z[j]]]==0);
cz[j][a[z[j]]]++;
cz[j+1][a[z[j]]]--;
ans[j+1]-=(cz[j+1][a[z[j]]]==0);
//这里要计算对下一块的影响
}
if(z[j]==n){eans=j;break;}
}
cout<<eans<<" ";
}
return 0;
}
```