整体二分挺好玩的...学一发
这个询问显然是可以二分的，但每次都二分就会T爆，所以我们有了“整体”二分
每次处理一些询问，要求这些询问的答案一定在$[l,r]$中
先把$l$到$mid$的操作实施，那么当前TAK的询问答案一定在$[l,mid]$中，当前NIE的询问答案一定在$[mid+1,r]$中，对答案为$[mid+1,r]$的那些询问加上$[l,mid]$的修改所产生的影响后分治处理即可
开始时加上一个操作$(1,m,+\infty)$就可以处理NIE的情况了
直接用线段树会被卡常，因为是区间加，单点询问，所以差分后用树状数组做即可
#include<stdio.h>
#include<vector>
using namespace std;
typedef long long ll;
const int inf=1000000000;
struct rain{int l,r,d;rain(int a=0,int b=0,int c=0){l=a;r=b;d=c;}
}R[300010];
vector<int>s[300010];
vector<int>::iterator it;
int p[300010],q[300010],ans[300010],ql[300010],qr[300010],n,m;
ll d[300010],las[300010];
int lowbit(int x){return x&-x;}
void add(int x,int v){while(x<=m){d[x]+=v;x+=lowbit(x);}
}
void add(int l,int r,int v){add(l,v);add(r+1,-v);
}
ll query(int x){ll s=0;while(x){s+=d[x];x-=lowbit(x);}return s;
}
void solve(int h,int t,int l,int r){if(h>t)return;int i,mid,cl,cr;ll tmp;if(l==r){for(i=h;i<=t;i++)ans[q[i]]=l;return;}mid=(l+r)>>1;for(i=l;i<=mid;i++){if(R[i].l<=R[i].r)add(R[i].l,R[i].r,R[i].d);else{add(R[i].l,m,R[i].d);add(1,R[i].r,R[i].d);}}cl=cr=0;for(i=h;i<=t;i++){tmp=0;for(it=s[q[i]].begin();it!=s[q[i]].end();it++){tmp+=query(*it);if(tmp+las[q[i]]>=p[q[i]])break;}if(tmp+las[q[i]]>=p[q[i]])ql[++cl]=q[i];else{las[q[i]]+=tmp;qr[++cr]=q[i];}}for(i=1;i<=cl;i++)q[h+i-1]=ql[i];for(i=1;i<=cr;i++)q[h+cl+i-1]=qr[i];for(i=l;i<=mid;i++){if(R[i].l<=R[i].r)add(R[i].l,R[i].r,-R[i].d);else{add(R[i].l,m,-R[i].d);add(1,R[i].r,-R[i].d);}}solve(h,h+cl-1,l,mid);solve(h+cl,t,mid+1,r);
}
int main(){int i,x,k;scanf("%d%d",&n,&m);for(i=1;i<=m;i++){scanf("%d",&x);s[x].push_back(i);}for(i=1;i<=n;i++)scanf("%d",p+i);scanf("%d",&k);for(i=1;i<=k;i++)scanf("%d%d%d",&R[i].l,&R[i].r,&R[i].d);R[++k]=rain(1,m,inf);for(i=1;i<=n;i++)q[i]=i;solve(1,n,1,k);for(i=1;i<=n;i++){if(ans[i]==k)puts("NIE");elseprintf("%d\n",ans[i]);}
}
