【Codeforces 786C】Till I Collapse | Mrsrz's blog

整除分块思想，二分，根号分治。

题目大意：

给定一个长度为 $n$ 的数列 $a_1,a_2,a_3,\ldots,a_n$，你要将其划分为最少的段，使得每个段里不同的数只有不超过 $m$ 个。

对于 $m\in [1,n]$ 都要求出答案。

题解：

对于一个 $m$，答案的上界为 $\lceil\frac nm\rceil$。

由整除分块的思想可以知道，这个的不同取值只有 $O(\sqrt n)$ 种，所以不同的答案只有 $O(\sqrt n)$ 种。

而且由于答案是单调不增的，所以相同的答案一定是连续出现。

所以我们有一个简单的做法：枚举每个答案未知的 $m$，$O(n)$ 求出它的答案，然后二分这个答案最右边的出现位置。

这个做法的时间复杂度为 $O(n\sqrt n\log n)$，并无法通过。

我们发现，当 $m$ 比较小的时候，这个答案相同的区间是很短的，但是每次都要在后面剩余的位置进行二分，这就非常不划算。

所以在 $m$ 比较小的时候，我们枚举每个位置并 $O(n)$ 求出答案，在 $m$ 比较大的时候用上面的方法求答案。

当阈值为 $\sqrt {n\log n}$ 时，总时间复杂度最优，为 $O(n\sqrt{n\log n})$。可以通过本题。

Code：

#include<cstdio>
const int N=1e5+8;
int n,a[N];
bool vis[N];
inline int solve(int m){
    int k=1,l=1,tot=0;
    for(int i=1;i<=n;++i)if(!vis[a[i]]){
        if(tot==m){
            for(int j=l;j<i;++j)vis[a[j]]=0;
            tot=0,++k,l=i;
        }
        ++tot,vis[a[i]]=1;
    }
    for(int i=l;i<=n;++i)vis[a[i]]=0;
    return k;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    for(int i=1;i<=1000&&i<=n;++i)printf("%d ",solve(i));
    for(int l=1001;l<=n;){
        int s=solve(l);
        int L=l+1,R=n,t=l;
        while(L<=R){
            const int mid=L+R>>1;
            if(solve(mid)==s)L=(t=mid)+1;else R=mid-1;
        }
        for(int i=l;i<=t;++i)printf("%d ",s);
        l=t+1;
    }
    return 0;
}