Meteors
格式难调，题面就不妨放了。
分析：
一道整体二分的练手题。
就是一般的整体二分的套路，但是要注意，将修改和询问加入队列的时候要先加修改再加询问。另外，博主代码打得太丑，常数贼大，不建议照这么打。。。
Code：
//It is made by HolseLee on 5th Oct 2018
//Luogu.org P3527
#include<bits/stdc++.h>
#define N 300007
using namespace std; typedef long long ll;
int n,m,K,cnt,ans[N];
ll c[N],a[N];
vector<int>G[N];
struct Node {
int x,y,pos,type; ll k;
}q[N<<],q1[N],q2[N]; inline ll read()
{
ll x=; char ch=getchar(); bool flag=false;
while( ch<'' || ch>'' ) {
if( ch=='-' ) flag=true; ch=getchar();
}
while( ch>='' && ch<='' ) {
x=(x<<)+(x<<)+(ch^); ch=getchar();
}
return flag ? -x : x;
} void print(int x)
{
if( x> ) print(x/);
putchar(x%+'');
} inline int lowbit(int x)
{
return x&(-x);
} inline void add(int pos,ll x)
{
for(; pos<=m; pos+=lowbit(pos)) c[pos]+=x;
} inline ll quary(int pos)
{
ll ret=;
for(; pos>; pos-=lowbit(pos)) ret+=c[pos];
return ret;
} void solve(int l,int r,int L,int R)
{
if( l>r || L>R ) return;
if( l==r ) {
for(int i=L; i<=R; ++i)
if( q[i].type== ) ans[q[i].pos]=l;
return;
}
int mid=(l+r)>>, cnt1=, cnt2=;
for(int i=L; i<=R; ++i)
if( q[i].type== ) {
ll tmp=;
for(int j=; j<G[q[i].pos].size(); ++j) {
tmp+=quary(G[q[i].pos][j]);
if( tmp>q[i].k ) break;
}
if( tmp>=q[i].k ) q1[++cnt1]=q[i];
else q[i].k-=tmp,q2[++cnt2]=q[i];
} else {
if( q[i].pos<=mid ) {
if( q[i].type== ) {
add(q[i].x,q[i].k), add(q[i].y+,-q[i].k);
} else {
add(,q[i].k), add(q[i].y+,-q[i].k), add(q[i].x,q[i].k);
}
q1[++cnt1]=q[i];
} else {
q2[++cnt2]=q[i];
}
}
for(int i=; i<=cnt1; ++i) {
if( q1[i].type== ) continue;
if( q1[i].type== ){
add(q1[i].x,-q1[i].k), add(q1[i].y+,q1[i].k);
} else {
add(,-q1[i].k), add(q1[i].y+,q1[i].k), add(q1[i].x,-q1[i].k);
}
}
for(int i=; i<=cnt1; ++i) q[L+i-]=q1[i];
for(int i=; i<=cnt2; ++i) q[L+cnt1+i-]=q2[i];
solve(l,mid,L,L+cnt1-); solve(mid+,r,L+cnt1,R);
} int main()
{
n=read(), m=read();
int x,y; ll z;
for(int i=; i<=m; ++i) G[read()].push_back(i);
for(int i=; i<=n; ++i) a[i]=read();
K=read();
for(int i=; i<=K; ++i) {
x=read(), y=read(), z=read();
q[++cnt].x=x, q[cnt].y=y, q[cnt].k=z; q[cnt].pos=i;
if( y>=x ) q[cnt].type=; else q[cnt].type=;
}
for(int i=; i<=n; ++i)
q[++cnt].pos=i, q[cnt].k=a[i], q[cnt].type=;
solve(,K+,,cnt);
for(int i=; i<=n; ++i)
if( ans[i]!=K+ ) print(ans[i]),putchar('\n');
else puts("NIE");
return ;
}