首先贪心是显然的,但是询问有n个
先考虑一个朴素的主席树做法
对于每个k,对于当前固定的L,二分R,用主席树查询一下[L,R]区间内的不同数个数是否大于K个(主席树的经典应用),更新答案,暴力跳过去
时间复杂度:一共有nlogN个区间(n/1+n/2+n/3~nlnN,调和级数知识)
二分的复杂度是logN,主席树查询的复杂度是logN,一共是N*(logN)^3,GET TLE!
////////////
"如果能省去二分的复杂度,在主席树上直接二分就很好了!"
参考别的博客有一个trick:倒序建主席树,第i棵主席树管理的是[i,n]之间有多少不同数
对于当前的a[i],它有效的区间其实是[ i, last[a[i]]-1 ] ,因为再往后,它已经出现过了,贡献都是一样的
区间更新的话同样差分就可以解决(可以参考主席树入门:求静态区间第k小)
经过这样的转换后查询r时直接在主席树上二分即可
对于当前结点的左子树,如果其cnt>k,则递归到左边;否则递归到右边
#include<bits/stdc++.h> #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int maxn=1e5+5; const int N=maxn<<6; int n; int node,rt[N]; struct tree{ int ls,rs,cnt; }t[N]; void update(int& p,int pos,int val,int l=1,int r=n+1){ t[++node]=t[p];t[node].cnt+=val;p=node; if(l==r){ return; } int mid=l+r>>1; if(pos<=mid) update(t[p].ls,pos,val,l,mid); else update(t[p].rs,pos,val,mid+1,r); } int query(int kth,int x,int l=1,int r=n+1){ if(l==r){ return l; } int mid=l+r>>1; int sum=t[t[x].ls].cnt; //cout<<"kth: "<<kth<<" x: "<<x<<" sum: "<<sum<<" "<<" [l,r]:"<<l<<" "<<r<<endl; if(sum>kth) return query(kth,t[x].ls,l,mid); else return query(kth-sum,t[x].rs,mid+1,r); } int a[maxn],last[maxn]; int main(){ fastio; //freopen("lys.in","r",stdin); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; update(rt[n],n,1); last[a[n]]=n; for(int i=n-1;i>=1;i--){ //cout<<i<<" th"<<endl; rt[i]=rt[i+1]; update(rt[i],i,1); if(last[a[i]]){ update(rt[i],last[a[i]],-1); } last[a[i]]=i; } for(int i=1;i<=n;i++){ int j=1,ans=0; while(j<=n){ //cout<<"j: "<<j<<endl; j=query(i,rt[j]); ans++; } cout<<ans<<" "; } }
标签:二分,Collapse,int,复杂度,Codeforces,Till,maxn,logN,主席 From: https://www.cnblogs.com/liyishui2003/p/17223744.html