题意: 体育课上,n个小朋友排成一行(从1到n编号),老师想把他们分成若干组,每一组都包含编号连续的一段小朋友,每个小朋友属于且仅属于一个组。 第i个小朋友希望它所在的组的人数不多于d[i],不少于c[i],否则他就会不满意。 在所有小朋友都满意的前提下,求可以分成的组的数目的最大值,以及有多少种分组方案最大,对10^9+7取模。 1<=n<=1000000 题解: 这题太神啦。。 我太菜了只想到nlog^2n的方法,果断tle,于是膜了题解 设f[i]表示前i个最多分多少组。 对于i>j,j是否能更新i取决于j< k<=i中c[k]的最大值和d[k]的最小值。 这个d的限制容易看出,满足的是[1,i]的某个后缀,并且有单调性,容易做出PRe[i]表示大于等于pre[i]的j满足d的限制。 还有c的限制,考虑用分治解决。函数solve(l,r)处理[l,r]之间的转移。 找到[l+1,r]中c最大值位置k。只要能处理[l,k-1]对[k,r]的转移就可以调用solve(l,k-1),solve(k,r)解决。 找这个位置分割的好处在于所有转移之间c的最大值都确定了。 i可用的j区间是[max(pre[i],l),min(k-1,i-c)] 然后对[max(k,l+c),r]的i分类转移。(注意pre是递增的,所以每一类都是连续的一段) 1、pre[i]< l && i<=k-1+c 这部分用的是一段前缀,并且注意i向后移一位,只会多一个可用的j。一开始用线段树查一次,然后每移一位暴力更新一次。 2、pre[i]< l && i>k-1+c 这部分用的是全部j。二分出这样的i区间,查一次然后区间更新。 3、l<=pre[i]< k 直接在线段树上查 4、pre[i]>=k 退出
然后分析复杂度 1是循环,2是二分然后线段树操作,3是循环线段树操作 分类讨论一下可以发现,1的循环次数不会大于两段中较短的。 2的复杂度logn,在分治结构里不影响复杂度 3的这部分,注意在整个算法中,更新i的区间是互不重叠的。这就代表包含pre[i]的区间只有一个,所以整体复杂度O(nlogn)。
分治内的复杂度T(n)=T(x)+T(n-x)+logn+min(x,n-x) 乍看一下不好分析 可我们考虑把分治看成一层一层,然后把从上往下分看成从下往上合 这不就是启发式合并的复杂度么 于是整体O(nlogn)
#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<iostream>#define N 1000010#define mmod 1000000007using namespace std;struct node{int lc,rc,c,d,f,g,k,lzf,lzg;}lt[2*N];int n,tl,f[N],g[N],pre[N];void comb(int &f,int &g,int ff,int gg){ if(ff>f) f=ff,g=gg; else if(f==ff) g=(g+gg)%mmod;}void down(int now){ int lc=lt[now].lc,rc=lt[now].rc; if(lc) comb(lt[lc].lzf,lt[lc].lzg,lt[now].lzf,lt[now].lzg); if(rc) comb(lt[rc].lzf,lt[rc].lzg,lt[now].lzf,lt[now].lzg); comb(lt[now].f,lt[now].g,lt[now].lzf,lt[now].lzg); lt[now].lzf=lt[now].lzg=0;}void upd(int now){ int lc=lt[now].lc,rc=lt[now].rc; if(lt[lc].lzf) down(lc); if(lt[rc].lzf) down(rc); if(lt[lc].c>lt[rc].c) lt[now].c=lt[lc].c,lt[now].k=lt[lc].k; else lt[now].c=lt[rc].c,lt[now].k=lt[rc].k; lt[now].d=min(lt[lc].d,lt[rc].d); if(lt[lc].f>lt[rc].f) lt[now].f=lt[lc].f,lt[now].g=lt[lc].g; else if(lt[lc].f<lt[rc].f) lt[now].f=lt[rc].f,lt[now].g=lt[rc].g; else lt[now].f=lt[lc].f,lt[now].g=(lt[lc].g+lt[rc].g)%mmod;}int find_d(int now,int l,int r){ int lc=lt[now].lc,rc=lt[now].rc,mid=(lt[now].l+lt[now].r)/2; if(lt[now].l==l && lt[now].r==r) return lt[now].d; if(mid>=r) return find_d(lc,l,r); else if(l>mid) return find_d(rc,l,r); else return min(find_d(lc,l,mid),find_d(rc,mid+1,r));}void find_c(int now,int l,int r,int &c,int &k){ int lc=lt[now].lc,rc=lt[now].rc,mid=(lt[now].l+lt[now].r)/2; if(lt[now].l==l && lt[now].r==r) {c=lt[now].c;k=lt[now].k;return;} if(mid>=r) find_c(lc,l,r,c,k); else if(l>mid) find_c(rc,l,r,c,k); else { int c1,c2,k1,k2;find_c(lc,l,mid,c1,k1);find_c(rc,mid+1,r,c2,k2); if(c1>c2) c=c1,k=k1; else c=c2,k=k2; }}void find(int now,int l,int r,int &f,int &g){ if(l>r) {f=-1;g=0;return;} int lc=lt[now].lc,rc=lt[now].rc,mid=(lt[now].l+lt[now].r)/2; if(lt[now].lzf) down(now); if(lt[now].l==l && lt[now].r==r) {f=lt[now].f;g=lt[now].g;return;} if(mid>=r) find(lc,l,r,f,g); else if(l>mid) find(rc,l,r,f,g); else { int ff,gg; find(lc,l,mid,f,g);find(rc,mid+1,r,ff,gg); comb(f,g,ff,gg); }}void change(int now,int l,int r,int f,int g,int ll,int rr){ int lc=lt[now].lc,rc=lt[now].rc,mid=(ll+rr)/2; if(lt[now].lzf) down(now); if(ll==l && rr==r) {comb(lt[now].lzf,lt[now].lzg,f,g);return;} if(mid>=r) change(lc,l,r,f,g,ll,mid); else if(l>mid) change(rc,l,r,f,g,mid+1,rr); else change(lc,l,mid,f,g,ll,mid),change(rc,mid+1,r,f,g,mid+1,rr); upd(now);}void bt(int l,int r){ int now=++tl; lt[now].l=l;lt[now].r=r; if(l<r) { int mid=(l+r)/2; lt[now].lc=tl+1;bt(l,mid); lt[now].rc=tl+1;bt(mid+1,r); upd(now); } else { lt[now].c=f[l];lt[now].k=l;lt[now].d=g[l]; if(l==0) lt[now].f=0,lt[now].g=1; else lt[now].f=-1,lt[now].g=0; }}void get_pre(){ int j=0; for(int i=1;i<=n;i++) { while(i-find_d(1,j+1,i)>j) j++; pre[i]=j; }}int td(int l,int r,int x){ int k; while(l<=r) { int mid=(l+r)/2; if(pre[mid]<x) k=mid,l=mid+1; else r=mid-1; } return k;}void make(int l,int r,int k,int c){ int st=max(k,l+c),ed=min(r,k-1+c),ff=-1,gg=0,i=st; while(i<=ed) { if(pre[i]>=k) return; if(pre[i]>=l) break; if(i==st) find(1,l,i-c,ff,gg); else comb(ff,gg,f[i-c],g[i-c]); if(ff!=-1) comb(f[i],g[i],ff+1,gg); i++; } if(i>r) return; if(pre[i]<l) { int x=td(i,r,l); find(1,l,k-1,ff,gg); if(ff!=-1) change(1,i,x,ff+1,gg); i=x+1; } while(i<=r) { if(pre[i]>=k) return; find(1,pre[i],min(k-1,i-c),ff,gg); if(ff!=-1) comb(f[i],g[i],ff+1,gg); i++; }}void solve(int l,int r){ if(l>r) return; if(l==r) {change(1,l,l,f[l],g[l]);find(1,l,l,f[l],g[l]);return;} int k,c;find_c(1,l+1,r,c,k); solve(l,k-1); make(l,r,k,c); solve(k,r);}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&f[i],&g[i]); bt(0,n); for(int i=1;i<=n;i++) f[i]=-1; for(int i=1;i<=n;i++) g[i]=0; g[0]=1; get_pre(); solve(0,n); if(f[n]==-1) printf("NIE/n"); else printf("%d %d/n",f[n],g[n]); return 0;}新闻热点
疑难解答