CF786c分块题解
思路：
首先思考一下如果直接硬着头皮做会怎么样？
对于每一个k，我都要遍历一遍数组贪心求解ans，导致n方时间复杂度
要发现一下性质：
- 答案最多为ceil(n/k)。
- 随着k的增加,答案单调不增。
- 随着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;
}
}