传送门
题意：给定一个环，每个节点有一个所属国家，k次事件，每次对[l,r]区间上的每个点点权加上一个值，求每个国家最早多少次操作之后所有点的点权和能达到一个值
题解：题目要求找到最小的事件使权值达到一个值，如果是只有一个国家，那很容易就能想到二分答案，判断枚举的数的合法性，在继续二分下去，找到最小值，但是对于多个国家复杂度就会多一个n——————TLE；
最开始想的时候还是想的二分答案，然后建一颗主席树，对于每次枚举的答案，通过主席树去判断答案的合法性，然后每一次的时间复杂度就是m1*logm*longk，总的时间复杂度就是m*logm*logk,然后发现空间过不了~~~；
然后就是整体二分这个东西了，二分的进阶版，我们同样去二分一个答案，对于不符合的国家，那么它的答案是比我们当前二分的值是要大的，所以将其划分到右区间，对于符合条件的就可以划分到左区间，然后递归的处理左右区间同时更新左右区间的端点值，最后维护出答案就好了（是不是特别简单）；
对于二分时的判断可以通过维护树状数组来完成，同过差分进行区间加减，判断时只需要判断属于国家的点上的值的合是不是满足要求的，然后维护树状数组只需要暴力维护就好，需要的部分保留或者添加，不需要的部分删除就好，不需要将树状数组清空。
AC代码
#include<stdio.h> #include<vector> #include<string.h> #include<algorithm> #include<iostream> #define ll long long using namespace std; const int maxn=3e5+5; //const ll inf=9223372036854775800; //const int inf=1e9; ll tree[maxn]; ll x1[maxn]; int ans[maxn],num[maxn]; vector<int> s1; struct node{ int l,r; ll va; }y[maxn]; struct node1{ int va,id; } s[maxn]; bool cmp(node1 a,node1 b){ return a.va<b.va; } int n,m; inline void add(int x,ll k){ while(x<maxn) tree[x]+=k,x+=(x&(-x)); } inline ll sum(int x){ ll k=0; while(x>0) k+=tree[x],x-=(x&(-x)); return k; } inline void work(int now,ll k){ ll va1=y[now].va*k; if(y[now].l>y[now].r) add(1,va1),add(y[now].r+1,-va1),add(y[now].l,va1),add(m+1,-va1); else add(y[now].l,va1),add(y[now].r+1,-va1); } inline void modify(int l1,int r1,ll k){ for(int i=l1;i<=r1;i++) work(i,k); } void cdq(vector<int> q,int l1,int r1,int k){ if(l1>r1){ for(int a=0;a<q.size();a++) ans[q[a]]=k; return ; } int mid=(l1+r1)>>1; modify(mid+1,r1,-1); vector<int> q1; vector<int> q2; int num1=0,num2=0; for(int a=0;a<q.size();a++){ int b=q[a]; ll su=0; for(int c=num[b-1]+1;c<=num[b];c++){ int d=s[c].id; su+=sum(d); if(su>=x1[b]) break; } //printf("%lld %d %d\n",su,mid,b); if(su>=x1[b]) q1.push_back(b),num1++; else q2.push_back(b),num2++; } modify(mid,mid,-1); if(num1) cdq(q1,l1,mid-1,mid); modify(mid,r1,1); if(num2) cdq(q2,mid+1,r1,k); } int main( ) { memset(tree,0,sizeof(tree)); scanf("%d %d",&n,&m); for(int a=0;a<=n;a++) num[a]=0; for(int a=1;a<=m;a++){ scanf("%d",&s[a].va); s[a].id=a; num[s[a].va]++; } sort(s+1,s+m+1,cmp); for(int a=1;a<=n;a++){ scanf("%lld",&x1[a]),s1.push_back(a); num[a]+=num[a-1]; } int k; scanf("%d",&k); for(int a=1;a<=k;a++) scanf("%d %d %lld",&y[a].l,&y[a].r,&y[a].va); modify(1,k,1); cdq(s1,1,k,0); for(int a=1;a<=n;a++){ if(ans[a]) printf("%d\n",ans[a]); else printf("NIE\n"); } }
