题外话
根分纸张第一次自己做出根分虽然很水，纪念一下。
\(\text{Links}\)
题意
给定一个长度为 \(n\) \((1\le n\le 10^5)\) 的序列 \(a\) \((1\le a_i\le n)\)，对于 \(k=1,2,3,\dots,n\)，分别求出最小的 \(m\)，使得存在一种将原序列划分成 \(m\) 段的方案，满足每段中不同的数字个数不超过 \(k\)。
Difficulty：*2400
题解
条件是关于不同数字的个数，看起来很奇怪。
要对于 \(n\) 个 \(k\) 都求解，但是感觉没有什么可以相互“继承”或者“转移”的地方，很奇怪。
但它长得很像二分，也有点像 \(dp\)，还有点像 \(ds\) 题，很奇怪。
这么多神秘的奇怪点，那估计是根分罢（大雾。
考虑给定一个 \(k\) 的时候如何求解。显然双指针 \(O(n)\) 扫一遍，每次在满足条件的情况下贪心地尽量扩展区间即可，正确性显然。
考虑发掘一下答案的性质，或者说答案和 \(k\) 的取值之间有没有什么联系。于是发现必然有 \(m\le \frac{n}{k}\)，因为每次尽量扩展区间的话，当前区间至少要有 \(k\) 个数才能满足有 \(k\) 个不同的数，然后再扩展才可能会变得不合法。
有了这个式子之后做法其实就比较显然了。
设置一个阈值 \(T\)，对于 \(k\le T\)，一个一个暴力 \(O(n)\) 扫。
对于 \(k\gt T\) 的话，可以发现答案具有单调性，即当 \(k\) 不断减小的时候，答案 \(m\) 一定是非降的。并且又因为此时答案 \(m\) 不会超过 \(\frac{n}{T}\)，所以我们可以枚举答案 \(m\) 的值，二分出它可以作为答案的区间，check 部分可以直接套用前面的 \(O(n)\) 做法。
这么看来这题是不是确实挺水的/kuk
时间复杂度为 \(O(Tn+\frac{n}{T}n\log n)\)，取 \(T=\sqrt{n\log n}\) 时候可达到平衡，实测下来也确实比取 \(T=\sqrt n\) 要快很多，在没开 \(O2\) 的情况下，最慢的测试点，前者大约跑了 \(1.0s\)，后者大约 \(1.8s\)。
\(\text{Code:}\)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define re register
const int N=100100;
int n,a[N],T,lgn,sq,fnans[N],cnt[N],res;
il int read(){
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
il void Add(int x){
if(!cnt[x])res++;
cnt[x]++;
}
il void Del(int x){
cnt[x]--;
}
il int solve(int k){
int tot=0,l=1,r=0;
for(re int i=1;i<=n;i++)cnt[i]=0;
res=0;
while(l<=n){
if(r<n){
Add(a[++r]);
if(res>k){
tot++;
int tmp=r;
while(l<=r)Del(a[l++]);
res=0,l=tmp,r=l-1;
}
}
else{
tot++;
break;
}
}
return tot;
}
il bool check(int m,int k){
return solve(k)<=m;
}
int main(){
n=read();
T=sqrt(max(n,n*__lg(n)));
for(re int i=1;i<=n;i++)a[i]=read();
for(re int k=1;k<=T;k++)fnans[k]=solve(k);
int T0=n/T;
if(n%T)T0++;
int lst=n+1;
for(re int m=1;m<=T0;m++){
int l=1,r=n,mid,ans;
while(l<=r){
if(check(m,mid=(l+r)>>1))ans=mid,r=mid-1;
else l=mid+1;
}
for(re int i=ans;i<lst;i++)
if(!fnans[i])fnans[i]=m;
lst=ans;
}
for(re int i=1;i<=n;i++)cout<<fnans[i]<<' ';
return 0;
}