CF786c分块题解

CF786c分块题解

思路：

首先思考一下如果直接硬着头皮做会怎么样？
对于每一个k，我都要遍历一遍数组贪心求解ans，导致n方时间复杂度

要发现一下性质：

1. 答案最多为ceil(n/k)。
2. 随着k的增加,答案单调不增。
3. 随着k的增加，答案越不容易改变(连续相同的答案越多)。

由1可知，总共的答案数量大概在根号n级别
由2可知，可以二分答案，寻找出连续一段k的答案是多少
由3可知，越到k大的地方，越容易二分出很长一段相同的答案，反之，在前面二分答案很多都是无效的
用根号n来区分前面和后面，前面暴力后面二分答案
前面时间复杂度：n * 根号n
后面时间复杂度：不会分析......
这样分析：
如果不分段的话，答案就是n * n * logn
然后答案最多根号n个，我二分又能找到一段的答案，所以应该是
n * 根号n * logn
假设我分的长度为s
那么变成了s * 根号n * logs+s * n
大概s在根号n的时候比较好

代码：

#include<bits/stdc++.h>
using namespace std;
int num[100006];
bool T[100005];
int n;
int work(int k){
    memset(T,0,sizeof(T));
    int sum = 0, cnt = 0, sta = 1;
    for(int i = 1; i <= n; ++ i){
        if(!T[num[i]]){
            T[num[i]] = 1, cnt ++;
        } 
        if(cnt > k){
            sum++, cnt = 1;
            for(int j = sta; j < i; ++ j){//如此来保证找一次用n的时间
                T[num[j]] = 0;
            } 
            T[num[i]] = 1; 
            sta = i;
        }
    }
    if(cnt){
        sum++;
    } 
    return sum;
}
int sq;
int main(){
	ios::sync_with_stdio(false);
	
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> num[i];
	}
	sq=ceil(1.0*sqrt(n));
    for(int i=1;i<=sq;i++){
        int ans=work(i);
        cout<<ans<<" ";
    }
    int now=sq+1;
    while(now<=n){
        int ans=work(now);
        int l=now;
        int r=n;
        while(l<=r-1){
            int mid=ceil(1.0*(l+r)/2);
            int ans2=work(mid);
            if(ans2<ans){
                r=mid-1;
            }
            else{
                l=mid;
            }
        }
        for(int i=now;i<=l;i++){
            cout<<ans<<" ";
        }
        now=l+1;
    }

}