题解 CF786C 【Till I Collapse】
ChthollyTree
2019-04-18 14:38:59
然而并不需要主席树
对于$k <= \sqrt{n}$的情况,暴力即可
对于$k > \sqrt{n}$ ,答案 $<= \frac{n}{k} < \sqrt{n}$
此时,最多只有sqrt(n)种答案,且答案随着k的增大而减小
所以我们可以二分
时间复杂度 $n\sqrt{n}log(n)$ 可以通过
当然可以微调边界 使得时间复杂度变为 $n\sqrt{nlogn}$
```
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
int n,m;
int a[MAXN];
int c[MAXN];
int ans[MAXN];
int solve(int x) {
int rt = 0,ans = 0;
int ls = 0;
memset(c,0,sizeof(c));
for(int i = 1; i <= n; i ++) {
c[a[i]] ++;
if(c[a[i]] == 1) {
rt ++;
}
if(rt > x) {
i --;
for(int j = ls; j <= i+1; j ++)
c[a[j]] --;
rt = 0;
ls = i+1;
ans ++;
}
}
ans ++;
return ans;
}
void orz(int l,int r)
{
int sl = solve(l),sr = solve(r);
if(sl == sr) {
for(int j = l; j <= r; j ++)
ans[j] = sl;
} else {
int mid = (l+r)>>1;
orz(l,mid);
orz(mid+1,r);
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> a[i];
int o = 0;
for(int i = 1; i*i <= n*log2(n); i ++)
{ o = i;
ans[i] = solve(i);
}
orz(o+1,n);
for(int i = 1; i <= n; i ++)
cout<<ans[i]<<"\n";
return 0;
}
```