题意：给你n个国家，m个观测点组成的环，每个观测点所属的国家，和每个国家所需要的陨石数，总共k波陨石向范围为（L，R）中的观测点提供a个陨石。问每个国家在第几波陨石降落的时候第一次获得所需要的陨石数量。
题解：整体二分法，类似于二分答案，每次将陨石波数二分为（L，mid）（mid+1，R），用线段树维护从第1波陨石到第mid波陨石降落时观测点陨石数量，（区间更新，单点查询），暴力判断当前mid波的陨石降落时是否能使这些国家集合满足需求，能满足要求的国家分到一组，不能满足需求则分到另一组，再分别继续进行二分陨石区间。
有一个坑点就是一个国家最多会得到(3*10^5)*(3*10^5)*10^9个陨石 爆long long = =（陨石波数*国家拥有观测点数*单次落下陨石数）
AC代码：
#include<stdio.h> #include<vector> #define N 300005 using namespace std; typedef long long ll; vector<ll>vt[N]; ll a[N]; ll need[N]; ll add[N*8]; ll ql[N],qr[N],qw[N]; ll ans[N]; ll q,n,m; ll S[N],newS[N],pos; void update(ll l,ll r,ll L,ll R,ll root,ll k) { if(l<=L&&R<=r) { add[root]+=k; return ; } ll mid=L+R>>1; if(mid>=r)update(l,r,L,mid,root<<1,k); else if(mid<l)update(l,r,mid+1,R,root<<1|1,k); else { update(l,mid,L,mid,root<<1,k); update(mid+1,r,mid+1,R,root<<1|1,k); } } ll query(ll x,ll L,ll R,ll root,ll ad) { if(L==R) return ad+add[root]; ll mid=L+R>>1; if(x<=mid)return query(x,L,mid,root<<1,ad+add[root]); else return query(x,mid+1,R,root<<1|1,ad+add[root]); } void solve(ll l,ll r,ll L,ll R) { ll mid=l+r>>1; while(pos<=mid) { update(ql[pos],qr[pos],0,2*m-1,1,qw[pos]); pos++; } while(pos>=mid+2) { pos--; update(ql[pos],qr[pos],0,2*m-1,1,-qw[pos]); } if(l==r) { for(ll i=L;i<=R;i++) { ll sum=0; ll flag=1; for(ll j=0;j<vt[S[i]].size();j++) { ll to=vt[S[i]][j]; sum+=query(to,0,2*m-1,1,0); sum+=query(to+m,0,2*m-1,1,0); if(sum>=need[S[i]]) { flag=0; break; } } if(!flag) ans[S[i]]=l; else ans[S[i]]=-1; } return ; } ll l1=L-1,l2=R+1; for(ll i=L;i<=R;i++) { ll sum=0; ll flag=1; for(ll j=0;j<vt[S[i]].size();j++) { ll to=vt[S[i]][j]; sum+=query(to,0,2*m-1,1,0); sum+=query(to+m,0,2*m-1,1,0); if(sum>=need[S[i]]) { flag=0; break; } } if(!flag) newS[++l1]=S[i]; else newS[--l2]=S[i]; } for(ll i=L;i<=R;i++) S[i]=newS[i]; if(l1!=L-1)solve(l,mid,L,l1); if(l2!=R+1)solve(mid+1,r,l2,R); } int main() { scanf("%lld%lld",&n,&m); for(ll i=0;i<m;i++) { scanf("%lld",&a[i]); vt[a[i]-1].push_back(i); } for(ll i=0;i<n;i++) scanf("%lld",&need[i]); scanf("%lld",&q); for(ll i=0;i<q;i++) { scanf("%lld%lld%lld",&ql[i],&qr[i],&qw[i]); ql[i]--;qr[i]--; if(qr[i]<ql[i])qr[i]+=m; } pos=0; for(ll i=0;i<n;i++)S[i]=i; solve(0,q-1,0,n-1); for(ll i=0;i<n;i++) { if(ans[i]==-1)printf("NIE\n"); else printf("%lld\n",ans[i]+1); } }