題意： 體育課上，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;}新聞熱點
疑難解答
