time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
解题思路
无法AC的暴力
从1到n枚举k，对于每一个k，从左到右贪心扫一遍序列，统计已有的颜色种类，如果种类数超过了就再分一组，将种类数置为1。扫完一遍就得到答案了。显然复杂度(O(n^2))过不了。于是有了两个方向的优化——枚举k太多了，减少枚举k的次数，“加剪枝”；对于固定的k，扫一遍太多了，对于每一个k，不老老实实扫序列，而是在序列上“跳着扫”。
加剪枝
剪枝是这样的——如果显然随着k的增加，答案是单调不下降的，所以如果(k==l)时和(k==r)时最少分组数量相同，即(ans[l]==ans[r])，那么k取值在([l,r])之间时，最少分组数量也是相同的。仿佛活在梦里哦……
举个例子，输入的序列是自然数1 2 3 4 5 6 7 8 9 10，当(k==5)时，显然答案是2，当(k==9)时，显然答案也是2，那么当(k==6、k==7、k==8)时，答案不用算就是2。过于暴力。
然后枚举k的方法类似线段树划分区间，看看k在最大时和最小时相不相等，不相等就二分，看k在最小时和中间值时相不相等，以此类推……
复杂度不会分析，应该和序列的形态有关，还和二分方式有关。
对于下面给的代码，本机（CPU为i7-8565U）实测，当输入长度为十万的自然数序列时，耗时1.3s，但是CF评测姬快，所以可以AC。
跳着扫
我们一步一步扫描序列时，当发现目前序列中颜色种数超过k，就分出新的一组。区间内的种数，然后联想到这题[SDOI2009]HH的项链（这篇博客貌似已经成为我的博客里被引用最多的一篇，当然只是自引），然后显然要在线做，于是单纯的权值线段树不够用了，上主席树，想到这篇HDU 5919 Sequence ll，每次从当前点开始向后跳k个1(把第一次出现的置为1)，这样子每次不用扫描总共n步了，只用跳ans[k]步就好，然后我们知道ans[k]不是很大(意会)，所以跑得快。
时间复杂度嘛，我们扫k次，总共要跳(sum_{i=1}^{n} ans[i])次（这篇博客说ans[k]总和大概是(nlog n)级别），每次在主席树上找下一个点的复杂度是一个log，于是总的复杂度就是(O(nlog ^2n))。
我觉得这两种优化可以综合一下诶……
源代码
使用了第一种优化
#include<stdio.h>
#include<string.h>
int n;
int a[100010];
int b[100010];//桶
int ans[100010];
int f(int k)
{
memset(b,0,sizeof(b));
int cnt=1,id=b[a[1]]=1;//分组内的颜色数量和当前组编号
for(int i=1;i<=n;i++)
{
if(b[a[i]]==id) continue;//同一组中再次出现的颜色
b[a[i]]=id;//或者说之前分走了一组，这是新的一组，该组中第一次出现这个颜色
cnt++;//该组中颜色数量加一
if(cnt>k)//该分新的一组了
{
b[a[i]]=++id;
cnt=1;
}
}
return id;
}
void solve(int kl,int kr)
{
ans[kl]=f(kl);
ans[kr]=f(kr);
if(ans[kl]==ans[kr])
{
for(int i=kl+1;i<kr;i++) ans[i]=ans[kl];
return;
}
int mid=kl+kr>>1;
solve(kl,mid);
solve(mid+1,kr);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",a+i);
solve(1,n);
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}