题目大意：
给定一个环，每个节点有一个所属国家，k次事件，每次对[l,r]区间上的每个点点权加上一个值，求每个国家最早多少次操作之后所有点的点权和能达到一个值。
思路：
整体二分（二分答案），对于每个国家，如果在m次事件后到达目标则放在左边，否则放在右边（用下标映射）。区间加用树状数组维护。
反思：
整体二分不熟练。二分计算时算到mid，now表示当前已经经历了几次事件（可进可退）。快速排序用的也是整体二分。
代码：
1 #include<cstdio> 2 #define ll long long 3 const int M=300005; 4 int n,m,i,k,now,a[M],p[M],s[M],e[M],id[M],di[M],nex[M],fir[M],ans[M]; 5 ll c[M];//now表示当前已经经历了几次事件 6 7 int read() 8 { 9 int x=0; char ch=getchar(); 10 while (ch<48 || ch>57) ch=getchar(); 11 while (ch>47 && ch<58) x=(x<<1)+(x<<3)+ch-48,ch=getchar(); 12 return x; 13 } 14 15 void add(int x,int y) { for (;x<=m;x+=x&-x) c[x]+=y; } 16 ll sum(int x) { ll ans=0; for (;x;x^=x&-x) ans=ans+c[x]; return ans; } 17 18 void solve(int L,int R,int l,int r) 19 { 20 if (L>R) return; 21 if (l==r) { for (;L<=R;++L) ans[id[L]]=l; return; } 22 int mid=l+r>>1,i,j,x=L-1,y=R+1; ll tot; 23 while (now<mid) 24 if (s[++now]<=e[now]) add(s[now],a[now]),add(e[now]+1,-a[now]); 25 else add(s[now],a[now]),add(1,a[now]),add(e[now]+1,-a[now]); 26 for (;now>mid;--now) 27 if (s[now]<=e[now]) add(s[now],-a[now]),add(e[now]+1,a[now]); 28 else add(s[now],-a[now]),add(1,-a[now]),add(e[now]+1,a[now]); 29 for (i=L;i<=R;++i) 30 { 31 for (j=fir[id[i]],tot=0;j && (tot=tot+sum(j))<p[id[i]];j=nex[j]); 32 if (tot<p[id[i]]) di[--y]=id[i]; else di[++x]=id[i]; 33 } 34 for (i=L;i<=R;++i) id[i]=di[i]; 35 solve(L,x,l,mid),solve(y,R,mid+1,r); 36 } 37 38 int main() 39 { 40 n=read(),m=read(); 41 for (i=1;i<=m;++i) nex[i]=fir[k=read()],fir[k]=i; 42 for (i=1;i<=n;++i) p[i]=read(),id[i]=i; 43 for (k=read()+1,i=1;i<k;++i) s[i]=read(),e[i]=read(),a[i]=read(); 44 s[k]=1,e[k]=m,a[i]=1000000000,solve(1,n,1,k); 45 for (i=1;i<=n;++i) 46 if (ans[i]==k) puts("NIE"); 47 else printf("%d\n",ans[i]); 48 return 0; 49 }
转载于:https://www.cnblogs.com/HHshy/p/7189593.html
相关资源：JAVA上百实例源码以及开源项目