题目大意：略
整体二分裸题
考虑只有一个国家的情况如何处理
对询问数量二分答案，暴力$O(m)$打差分，求前缀和验证，时间是$O(mlogK)$
如果有$n$个国家，就是$O(nmlogK)$，非常不优秀的时间复杂度
发现我们对于每个国家都进行一次二分很浪费时间
考虑把国家分成一定数量的集合
每次二分出一个答案$mid$
把集合内的国家按照能否满足要求分成两个集合$S1,S2$
如果能满足要求，当前询问的mid不一定是最优解，答案范围一定是$[l,mid]$
如果不能满足要求，当前$mid$不能作为答案，答案范围只能是$[mid+1,r]$
$(l,mid,S1),(mid+1,r,S2)$递归分治处理，用树状数组维护即可
时间$O((K+n)logKlogm)$
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 300100
#define ll long long
#define dd double
#define inf 233333333
using namespace std; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
}
int n,m,Q,K;
struct BIT{
ll sum[N1];
void update(int x,int w){ for(int i=x;i<=m;i+=(i&(-i))) sum[i]+=w; }
ll query(int x){ ll ans=; for(int i=x;i;i-=(i&(-i))) ans+=sum[i]; return ans; }
void clr(int x){ for(int i=x;i<=m;i+=(i&(-i))) sum[i]=; }
}s;
struct node{int l,r,w;}q[N1];
vector<int>son[N1];
int que[N1*],tl,ans[N1],id[N1],tmp[N1],p[N1];
void alldic(int l,int r,int ql,int qr)
{
if(l>r||ql>qr) return;
int qmid=(ql+qr)>>,i,j,x,S=l,E=r; ll res;
for(i=ql;i<=qmid;i++)
{
if(q[i].l<=q[i].r){
s.update(q[i].l,q[i].w); s.update(q[i].r+,-q[i].w);
que[++tl]=q[i].l; que[++tl]=q[i].r+;
}else{
s.update(q[i].l,q[i].w); s.update(,q[i].w); s.update(q[i].r+,-q[i].w);
que[++tl]=; que[++tl]=q[i].l; que[++tl]=q[i].r+;
}
}
for(i=l;i<=r;i++)
{
x=id[i]; res=p[x];
for(j=;j<son[x].size();j++)
{
res-=s.query(son[x][j]);
if(res<=) { ans[x]=qmid; tmp[S++]=x; break;}
}
if(res>) { p[x]=res; tmp[E--]=x; }
}
for(i=l;i<=r;i++) id[i]=tmp[i];
while(tl) s.clr(que[tl--]);
alldic(l,S-,ql,qmid-); alldic(E+,r,qmid+,qr);
} int main()
{
scanf("%d%d",&n,&m);
int i,j,k,x,y,z;
for(i=;i<=m;i++){ x=gint(),son[x].push_back(i); }
for(i=;i<=n;i++){ p[i]=gint(); id[i]=i;}
scanf("%d",&Q);
for(i=;i<=Q;i++){ q[i].l=gint(); q[i].r=gint(); q[i].w=gint(); }
alldic(,n,,Q);
for(i=;i<=n;i++)
{
if(!ans[i]) puts("NIE");
else printf("%d\n",ans[i]);
}
return ;
}