正题

题目链接:https://www.luogu.com.cn/problem/CF786C

---

题目大意

给出一个长度为\(n\)的序列。

对于每个\(k\in[1,n]\)求将\(n\)分成最少的段使得每段的长度不同。

\(1\leq a_i\leq n\leq 10^5\)

---

解题思路

考虑对于一个\(k\)我们的做法显然就是直接暴力往后匹配能多晚分段就多晚分段。

然后考虑这题因为对于一个\(k\)答案的上界是\(\frac{n}{k}\)所以其实所有\(k\)的段数和是\(n\log n\)级别的。

所以我们可以所有的\(k\)一起做，用优先队列维护所有\(k\)的目前段结尾，然后每个数字记一下后面和他相等的第一个位置，在树状数组上倍增出需要的位置就好了。

时间复杂度\(O(n\log^2 n)\)

---

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define mp(x,y) make_pair(x,y)

#define lowbit(x) (x&-x)

using namespace std;

const int N=1e5+10;

int n,a[N],c[N],nxt[N],t[N],f[N];

priority_queue<pair<int,int> > q;

void Change(int x,int val){

	while(x<=n){

		t[x]+=val;

		x+=lowbit(x);

	}

	return;

}

int Ask(int k){

	int ans=0,x=0;

	for(int i=18;i>=0;i--)

		if(x+(1<<i)<=n&&ans+t[x+(1<<i)]<=k)

			x+=(1<<i),ans+=t[x];

	return x;

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]),c[i]=n+1;

 	for(int i=n;i>=1;i--)nxt[i]=c[a[i]],c[a[i]]=i;

	for(int i=1;i<=n;i++)Change(c[i],1);

	for(int i=1;i<=n;i++)q.push(mp(-1,i));

	for(int i=1;i<=n;i++){

		while(-q.top().first==i){

			int k=q.top().second;q.pop();

			f[k]++;q.push(mp(-Ask(k)-1,k));

		}

		Change(i,-1);Change(nxt[i],1);

	}

	for(int i=1;i<=n;i++)printf("%d ",f[i]);

	return 0;

}