CF787E. Till I Collapse（主席树）
E. Till I Collapse
题目大意
给你n个数让你划分区间，每个区间最多有k种不同的数，求划分的最少区间，输出k从1到n的答案。
思路
倒序建主席树，记录这个数上一次出现是什么时候，以坐标为主席树的根节点，建坐标线段树，对于每个数的位置+1，上一次出现的位置-1，这样树上值为1的坐标点x上的数a[x]都是不相同的,这样就可以枚举左端点去，查询右端点，这样就可以找到一个最远的区间个数为k的右端点，显然可以贪心的把这个当作一个区间，然后把右端点+1的点当作左端点去找下一个区间，这样就可以找出所有区间。最多有nlogn个区间所以复杂度O(nlognlogn)
代码
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define mes(p) memset(p,0,sizeof(p))
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sz(x) (int)x.size()
#define pb push_back
#define ls (rt<<1)
#define rs (ls|1)
#define all(x) x.begin(),x.end()
const int maxn=100005;
typedef long long ll;
typedef vector <int > vi;
typedef pair <int, int> pi;
int cnt,last[maxn], a[maxn], n;
int T[maxn];
struct node{
int sum,l,r;
}t[maxn<<7];
void update(int pre,int &now,int l,int r,int x,int val){
now = ++cnt;
t[now].sum = t[pre].sum + val;
t[now].l = t[pre].l;
t[now].r = t[pre].r;
if(l==r) return ;
int mid = l+r >> 1;
if(x<=mid) update(t[pre].l,t[now].l,l,mid,x,val);
else update(t[pre].r,t[now].r,mid+1,r,x,val);
}
int qr(int x,int l,int r,int k){
if(l==r){
if(t[x].sum<=k) return l;
else return l-1;
}
int mid = l+r >>1;
if(t[t[x].l].sum<= k) return qr(t[x].r,mid+1,r,k-t[t[x].l].sum);
else return qr(t[x].l,l,mid,k);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>> n ;
rep(i,1,n+1) cin>>a[i];
for(int i=n;i>=1;i--){
if(last[a[i]]){
update(T[i+1],T[i],1,n,last[a[i]],-1);
update(T[i],T[i],1,n,i,1);
}else update(T[i+1],T[i],1,n,i,1);
last[a[i]] = i;
}
for(int k=1;k<=n;k++){
int l=1,r=-1,ans = 0;
while(l<=n){
r = qr(T[l],1,n,k);
l = r+1;
ans ++;
}
cout << ans << " ";
}
return 0;
}
转载于:https://www.cnblogs.com/seast90/p/10835712.html
