题解 CF786C 【Till I Collapse】

ChthollyTree

2019-04-18 14:38:59

Solution

然而并不需要主席树 对于$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; } ```