题意: 给出一个长度为n的序列,每个数值在1-n之间且为整数,现在要把这个序列划分为若干段,使得每一段的颜色种数不超过k,求最少的区间数目.对于从1到n的n种k的取值,分别输出这时的最少区间数目. 分析:首先这个题很像HH的项链,而HH的项链的在线做法需要写可持久化线段树,我们自然想到这个题也需要可持久化线段树 考虑对于每个k分别求解.暴力的贪心做法是这样:从左端开始,每次找出一段尽量长的颜色种数不超过k的区间划分出来.如果颜色种数要求不超过k,那么划分的区间段数最多为n/k上取整.(k个元素一段即可).对于k的n种取值,一共最多要找nln(n)段区间.如果能在较低的复杂度(例如logn)内找出每一段区间,这个题就做出来了. 然后我的想法是类似bzoj4504 K个串,写了一发区间修改的可持久化线段树,然后每次在线段树上二分.Codeforces的官方题解大概相当于这个做法差分一下,不需要区间修改,只需要单点修改的可持久化线段树. 具体是:对于每个左端点L,我们求出一个数组f[L][],f[L][i]存储从L到i出现的不同颜色的种数(如果i<L那么f[L][i]=0).那么从F[L][]到F[L-1][],只有a[L-1]影响的一段区间的数值会+1,那么可以用可持久化线段树来维护这个序列.查询时如果二分答案,每次在线段树上查询是两个log,直接在线段树上二分(也就是在每个节点判断向左侧还是右侧递归求解)就是一个log的.我写了一发标记永久化.细节参见代码.
#include<cstdio> #include<algorithm> using namespace std; const int maxn=100005; struct node{ int Max,mk; node* ch[2]; node(){} node(int x,int y){ ch[0]=ch[1]=0;Max=x;mk=y; } }t[maxn*60];int tsz=0; node* root[maxn]; node* newnode(int x,int y){ t[++tsz]=node(x,y);return t+tsz; } int a[maxn]; int last[maxn]; void Insert(node* rt0,node* &rt,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr){ rt=newnode(rt0->Max+1,rt0->mk+1); rt->ch[0]=rt0->ch[0];rt->ch[1]=rt0->ch[1]; }else{ rt=newnode(0,rt0->mk); rt->ch[0]=rt0->ch[0];rt->ch[1]=rt0->ch[1]; int mid=(l+r)>>1; if(ql<=mid)Insert(rt0->ch[0],rt->ch[0],l,mid,ql,qr); if(qr>mid)Insert(rt0->ch[1],rt->ch[1],mid+1,r,ql,qr); rt->Max=max(rt->ch[0]->Max,rt->ch[1]->Max)+rt0->mk; } } int n; int query(node* rt,int l,int r,int lim,int pre){ if(l==r){//printf("%d\n",pre); if(pre+rt->Max>lim)return -1; else return l; } int lmax=rt->ch[0]->Max+pre+rt->mk; int mid=(l+r)>>1; if(lmax>lim)return query(rt->ch[0],l,mid,lim,pre+rt->mk); else if(lmax<lim)return query(rt->ch[1],mid+1,r,lim,pre+rt->mk); int t=query(rt->ch[1],mid+1,r,lim,pre+rt->mk); if(t==-1)return mid; else return t; } int right(int s,int lim){ return query(root[s],1,n,lim,0); } int work(int lim){ int pt=1; int ans=0; while(pt<=n){ ans++; pt=right(pt,lim)+1;//if(lim==1)printf("%d\n",pt); } return ans; } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",a+i); root[n+1]=newnode(0,0); root[n+1]->ch[0]=root[n+1]->ch[1]=root[n+1]; for(int i=1;i<=n;++i)last[i]=n+1; for(int i=n;i>=1;--i){ root[i]=root[i+1]; Insert(root[i],root[i],1,n,i,last[a[i]]-1); last[a[i]]=i; } // printf("%d\n",query(root[1],1,n,1,0));return 0; for(int i=1;i<=n;++i){ printf("%d ",work(i)); } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/6952508.html
相关资源：数据结构—成绩单生成器