CF E. Till I Collapse 整体二分+根号分治

#include <bits/stdc++.h> 
#define N 100003 
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;   
int A[N],C[N],ans[N],n;         
int solve(int x) 
{ 
    int cur=0,ans=0,ls=0,i,j,rt=0;  
    memset(C,0,sizeof(C));    
    for(i=1;i<=n;++i) 
    {  
        ++C[A[i]];      
        if(C[A[i]]==1) 
        {
            ++rt; 
        } 
        if(rt>x) 
        {
            --i;     
            for(j=ls;j<=i+1;++j) C[A[j]]--;               
            rt=0,ls=i+1,++ans; 
        }
    } 
    ++ans;
    return ans; 
}    
void div_con(int l,int r) 
{
    int L=solve(l), R=solve(r);  
    if(L==R) 
    {
        for(int j=l;j<=r;++j) ans[j]=L; 
    }
    else 
    {
        int mid=(l+r)>>1;   
        div_con(l,mid), div_con(mid+1,r);   
    }
}
int main() 
{
    int i,j; 
    // setIO("input");    
    scanf("%d",&n);       
    for(i=1;i<=n;++i) scanf("%d",&A[i]);    
    for(i=1;i*i<=n;++i) ans[i]=solve(i);     
    div_con(i, n);   
    for(i=1;i<=n;++i) printf("%d ",ans[i]); 
    return 0; 
}