简要题意
有 \(n\) 个国家和有 \(m\) 段的 环形 轨道。轨道的第 \(i\) 段有第 \(o_i\) 个国家建立的空间站。
有 \(k\) 个时刻，第 \(i\) 个时刻会在 \([l_i,r_i]\) 的轨道中降下 \(a_i\) 个陨石。
第 \(i\) 个国家需要至少 \(p_i\) 个陨石。你需要求出对于每一个国家，收集到足量陨石的最小时刻。如果不可能收集到足量陨石，输出 NIE。
\(1 \leq n,m,k \leq 3 \times 10^5,1 \leq p_i,a_i \leq 10^9\)，时间限制 \(2500\text{ms}\)，空间限制 \(512\text{MB}\)。
思路
下文中假设 \(n,m,k\) 同阶。
对于环形轨道，我们套路破环成链。然后就可以看成一个长度为 \(2m\) 的序列上的问题。
然后考虑这道题如果只询问一个国家怎么做。我们可以二分这个答案（答案显然具有单调性），检验答案时先将这之前的流星雨落下来，然后判断这个国家所有空间站接收到的陨石和是否满足条件。这样子可以使用树状数组优化到 \(O(n\log^2 n)\)。
按照这个思路，求出每一个国家的时间复杂度为 \(O(n^2\log^2 n)\)。无法通过本题。
我们会发现：每个国家在二分时，前几步很可能是一样的。这样子的话如果还是分开二分就很憨了。
我们考虑对于所有国家一起二分，将国家分成两拨，一拨满足，一拨不满足，然后分治。这就是整体二分。
可是这样子时间复杂度没有任何变化。因为 check 函数还是分开的。但是 check 函数合在一起又不现实。这里有一个很常用的 trick：
我们考虑当前二分答案区间为 \([l,r]\)。取 \(m=\lfloor\frac{l+r}{2}\rfloor\)。这时我们仅仅降下 \([l,m]\) 的流星雨。然后判断国家们是否够，如果不够，那么当前肯定小于 \([l,m]\) 的流星雨对其的陨石数，我们可以把它需要的减去 \([l,m]\) 这个国家的陨石和。（这时它需要的陨石个数的意义在答案二分区间中）
容易证明这个方法是正确的。
这个小 trick 可以将时间复杂度降低为 \(O(n\log^2 n)\)（具体证明见线段树的空间复杂度证明，这道题的时间复杂度证明与其类似）；
代码
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N = 6e5+5;
unsigned int t[N];
int n,m,k,ans[N];
struct queries{int l,r,a;} q[N];
struct country{int nd,id;} p[N],pl[N],pr[N];
vector<int> stations[N];
inline void update(int p,int v){for(;p<=(m<<1);p+=lowbit(p)) t[p]+=v;}
inline void update(int l,int r,int v){update(l,v);update(r+1,-v);}
inline unsigned int _query(int p){unsigned int ret=0;for(;p;p-=lowbit(p)) ret+=t[p];return ret;}
inline unsigned int query(int p){return _query(p)+_query(p+m);}
unsigned int got(int x){
unsigned int ret=0;
for(int i : stations[p[x].id]) ret += query(i);
return ret;
}
void solve(int ql,int qr,int l,int r){
if(ql>qr||l>r) return;
if(l==r){
for(int i=ql;i<=qr;i++) ans[p[i].id]=l;
return;
}
int mid=((l+r)>>1),pltot=0,prtot=0;
for(int i=l;i<=mid;i++) update(q[i].l,q[i].r,q[i].a);
for(int i=ql;i<=qr;i++){
unsigned int v=got(i);
if(v>=p[i].nd) pl[++pltot]=p[i];
else p[i].nd-=v,pr[++prtot]=p[i];
}
for(int i=ql;i<=(ql+pltot-1);i++) p[i]=pl[i-ql+1];
for(int i=(ql+pltot);i<=qr;i++) p[i]=pr[i-ql-pltot+1];
for(int i=l;i<=mid;i++) update(q[i].l,q[i].r,-q[i].a);
solve(ql,ql+pltot-1,l,mid);solve(ql+pltot,qr,mid+1,r);
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1,o;i<=m;i++){cin>>o;stations[o].push_back(i);}
for(int i=1;i<=n;i++){cin>>p[i].nd;p[i].id=i;}
cin>>k;
for(int i=1;i<=k;i++){cin>>q[i].l>>q[i].r>>q[i].a;q[i].r+=((q[i].r<q[i].l)*m);}
q[++k]={1,(m<<1),INT_MAX};
solve(1,n,1,k);
for(int i=1;i<=n;i++){
if(ans[i]!=k) cout<<ans[i]<<'\n';
else cout<<"NIE\n";
}
return 0;
}