给定一个环，每个节点有一个所属国家，k次事件，每次对[l,r]区间上的每个点点权加上一个值，求每个国家最早多少次操作之后所有点的点权和能达到一个值
非常好的整体二分模板题
之前的修改和询问都是全部扔到结构体里面一起分治的 这题不用这样（因为是先修改后询问的） 所以只对询问进行分治即可 可以减少很多码量 （但之前的模板题不适合这样 之前二分的为值域 如果遍历值域的话复杂度太高了 这题二分的不是自然数值域 而是操作次数！）
注意给定的是一个环 所以当处理左端点大于右端点的区间时 将右端点加上区间长度(也就是展开成一条链 ） 同时在树状数组询问的时候要加上两个值（一个值比另一个大m）
二分的右界+1 当均不满足的时候 跳到右界+1
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=2e6+10; int n,m,ans[N],zuo[N],you[N],pos,head[N],k,x; ll v[N],t[N]; struct Edge{int to,nex;}edge[N<<1]; void add(int a,int b){edge[++pos]=(Edge){b,head[a]};head[a]=pos;} void upnode(int x,int v){for(;x<=N;x+=x&-x)t[x]+=v;} ll qsum(int x){ll ans=0;for(;x;x-=x&-x)ans+=t[x];return ans;} struct node{ll id,need;}s[N],temp1[N],temp2[N]; void solve(int L,int R,int l,int r) { if(l>r)return ; if(L==R){rep(i,l,r)ans[s[i].id]=L;return ;} int mid=(L+R)>>1; rep(i,L,mid)upnode(zuo[i],v[i]),upnode(you[i]+1,-v[i]); int cnt1=0,cnt2=0; rep(i,l,r) { ll sum=0; for(int j=head[s[i].id];j&&sum<=s[i].need;j=edge[j].nex) sum+=qsum(edge[j].to)+qsum(edge[j].to+m); if(sum>=s[i].need)temp1[++cnt1]=s[i]; else temp2[++cnt2]=s[i],temp2[cnt2].need-=sum; } rep(i,L,mid)upnode(zuo[i],-v[i]),upnode(you[i]+1,v[i]);//谁污染谁治理 rep(i,1,cnt1)s[l-1+i]=temp1[i]; rep(i,1,cnt2)s[l+cnt1-1+i]=temp2[i]; solve(L,mid, l,l+cnt1-1);solve(mid+1,R,l+cnt1,r); } int main() { scanf("%d%d",&n,&m); rep(i,1,m)scanf("%d",&x),add(x,i); rep(i,1,n)scanf("%lld",&s[i].need),s[i].id=i; scanf("%d",&k); rep(i,1,k){scanf("%d%d%lld",&zuo[i],&you[i],&v[i]);if(you[i]<zuo[i])you[i]+=m;} solve(1,k+1,1,n); rep(i,1,n) if(ans[i]==k+1)printf("NIE "); else printf("%d ",ans[i]); return 0; }