题意

给定一个环，每个节点有一个所属国家，k次事件，每次对[l,r]区间上的每个点点权加上一个值，求每个国家最早多少次操作之后所有点的点权和能达到一个值

题解

一个一个国家算会T。

这题要用整体二分。我们二分mid给所有国家判断。把可以满足条件的国家放在左边，把所有不满足的国家放在右边。然后继续递归。

本题要求区间加减单点查询。所以套树状数组维护。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 const long long N=300010; 9 const long long INF=1e9+1;10 vector
            
              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){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
              
               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\n");94 else printf("%lld\n",ans[i]);95 }96 return 0;97 }