题意
给定一个环，每个节点有一个所属国家，k次事件，每次对[l,r]区间上的每个点点权加上一个值，求每个国家最早多少次操作之后所有点的点权和能达到一个值
题解
一个一个国家算会T。
这题要用整体二分。我们二分mid给所有国家判断。把可以满足条件的国家放在左边，把所有不满足的国家放在右边。然后继续递归。
本题要求区间加减单点查询。所以套树状数组维护。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<algorithm> 6 #include<vector> 7 using namespace std; 8 const long long N=300010; 9 const long long INF=1e9+1; 10 vector<long long> belong[N]; 11 long long c[N]; 12 long long n,m,target[N],con[N],ls[N],rs[N],val[N],ans[N],k; 13 long long now,LL[N],RR[N],sum[N]; 14 long long lowbit(long long x){ 15 return x&-x; 16 } 17 void add(long long x,long long w){ 18 for(long long i=x;i<=m;i+=lowbit(i)){ 19 c[i]+=w; 20 } 21 } 22 long long check(long long x){ 23 long long tmp=0; 24 for(long long i=x;i>=1;i-=lowbit(i)){ 25 tmp+=c[i]; 26 } 27 return tmp; 28 } 29 void change(long long l,long long r,long long w){ 30 if(l<=r){ 31 add(l,w);add(r+1,-w); 32 } 33 else { 34 add(l,w);add(m+1,-w); 35 add(1,w);add(r+1,-w); 36 } 37 } 38 void query(long long l,long long r,long long L,long long R){ 39 if(l>r)return ; 40 if(L>R)return ; 41 if(l==r){ 42 for(long long i=L;i<=R;i++){ 43 ans[con[i]]=l; 44 } 45 return; 46 } 47 long long mid=l+r>>1; 48 while(now<mid){ 49 now++; 50 change(ls[now],rs[now],val[now]); 51 } 52 while(now>mid){ 53 change(ls[now],rs[now],-val[now]); 54 now--; 55 } 56 for(long long i=L;i<=R;i++){ 57 sum[con[i]]=0; 58 for(long long j=0;j<belong[con[i]].size();j++){ 59 sum[con[i]]+=check(belong[con[i]][j]); 60 if(sum[con[i]]>target[con[i]])break; 61 } 62 } 63 long long rcnt=0;long long lcnt=0; 64 for(long long i=L;i<=R;i++){ 65 if(sum[con[i]]>=target[con[i]])LL[++lcnt]=con[i]; 66 else RR[++rcnt]=con[i]; 67 } 68 for(long long i=1;i<=lcnt;i++)con[i+L-1]=LL[i]; 69 for(long long i=1;i<=rcnt;i++)con[i+L-1+lcnt]=RR[i]; 70 query(l,mid,L,L+lcnt-1); 71 query(mid+1,r,L+lcnt,R); 72 } 73 int main(){ 74 scanf("%lld%lld",&n,&m); 75 for(long long i=1;i<=m;i++){ 76 long long a; 77 scanf("%lld",&a); 78 belong[a].push_back(i); 79 } 80 for(long long i=1;i<=n;i++){ 81 scanf("%lld",&target[i]); 82 con[i]=i; 83 } 84 scanf("%lld",&k); 85 for(long long i=1;i<=k;i++){ 86 scanf("%lld%lld%lld",&ls[i],&rs[i],&val[i]); 87 } 88 k++; 89 ls[k]=1;rs[k]=m;val[k]=INF; 90 now=0; 91 query(1,k,1,n); 92 for(long long i=1;i<=n;i++){ 93 if(ans[i]==k)printf("NIE "); 94 else printf("%lld ",ans[i]); 95 } 96 return 0; 97 }