Meteors

格式难调，题面就不妨放了。

---

　　分析：

　　一道整体二分的练手题。

　　就是一般的整体二分的套路，但是要注意，将修改和询问加入队列的时候要先加修改再加询问。另外，博主代码打得太丑，常数贼大，不建议照这么打。。。

　　Code：

 

//It is made by HolseLee on 5th Oct 2018//Luogu.org P3527#include
     
      #define N 300007using namespace std;typedef long long ll;int n,m,K,cnt,ans[N];ll c[N],a[N];vector
      
       G[N];struct Node {  int x,y,pos,type; ll k;}q[N<<1],q1[N],q2[N];inline ll read(){  ll x=0; char ch=getchar(); bool flag=false;  while( ch<'0' || ch>'9' ) {    if( ch=='-' ) flag=true; ch=getchar();  }  while( ch>='0' && ch<='9' ) {    x=(x<<1)+(x<<3)+(ch^48); ch=getchar();  }  return flag ? -x : x;}void print(int x){  if( x>9 ) print(x/10);  putchar(x%10+'0');}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=0;  for(; pos>0; 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==1 ) ans[q[i].pos]=l;    return;  }  int mid=(l+r)>>1, cnt1=0, cnt2=0;  for(int i=L; i<=R; ++i)    if( q[i].type==1 ) {      ll tmp=0;      for(int j=0; j
       
        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==2 ) {      add(q[i].x,q[i].k), add(q[i].y+1,-q[i].k);    } else {      add(1,q[i].k), add(q[i].y+1,-q[i].k), add(q[i].x,q[i].k);    }    q1[++cnt1]=q[i];      } else {    q2[++cnt2]=q[i];      }    }  for(int i=1; i<=cnt1; ++i) {    if( q1[i].type==1 ) continue;    if( q1[i].type==2 ){      add(q1[i].x,-q1[i].k), add(q1[i].y+1,q1[i].k);    } else {      add(1,-q1[i].k), add(q1[i].y+1,q1[i].k), add(q1[i].x,-q1[i].k);    }  }  for(int i=1; i<=cnt1; ++i) q[L+i-1]=q1[i];  for(int i=1; i<=cnt2; ++i) q[L+cnt1+i-1]=q2[i];  solve(l,mid,L,L+cnt1-1); solve(mid+1,r,L+cnt1,R);}int main(){  n=read(), m=read();  int x,y; ll z;  for(int i=1; i<=m; ++i) G[read()].push_back(i);  for(int i=1; i<=n; ++i) a[i]=read();  K=read();  for(int i=1; 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=2; else q[cnt].type=3;   }  for(int i=1; i<=n; ++i)    q[++cnt].pos=i, q[cnt].k=a[i], q[cnt].type=1;  solve(1,K+1,1,cnt);  for(int i=1; i<=n; ++i)    if( ans[i]!=K+1 ) print(ans[i]),putchar('\n');    else puts("NIE");  return 0;}