整体二分

先二分一个答案，判断是否可行，把可行的全都扔到左边，不可行的扔到右边

判断是否可行用树状数组就行

具体细节看代码好了

整体二分细节真多……也可能是我大脑已经退化了？

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #define ll long long 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf;10 inline ll read(){11     #define num ch-'0'12     char ch;bool flag=0;ll res;13     while(!isdigit(ch=getc()))14     (ch=='-')&&(flag=true);15     for(res=num;isdigit(ch=getc());res=res*10+num);16     (flag)&&(res=-res);17     #undef num18     return res;19 }20 const int N=700005;21 int n,m,k,ans[N],mb[N],st[N],top;22 ll c[N];23 vector
         
           a[N];24 struct node{25     int l,r,op,id;ll k;26     node(){}27     node(int l,int r,int op,int id,ll k):l(l),r(r),op(op),id(id),k(k){}28 }q[N],q1[N],q2[N];29 inline void add(int x,ll y){30     for(;x<=m;x+=x&-x){31         if(!c[x]) st[++top]=x;32         c[x]+=y;33     }34 }35 ll query(int x){36     ll res=0;37     for(;x;x-=x&-x) res+=c[x];38     return res;39 }40 void solve(int l,int r,int ql,int qr){41     if(l>r) return;42     if(ql==qr){43         for(int i=l;i<=r;++i) 44         if(q[i].op==1) ans[q[i].id]=ql;45         return;46     }47     int mid=ql+qr>>1,p1=0,p2=0;48     for(int i=l;i<=r;++i){49         switch(q[i].op){50             case 1:{51                 ll res=0;52                 for(int j=0,s=a[q[i].id].size();j
          
           =q[i].k) break;55 }56 if(res>=q[i].k) q1[++p1]=q[i];57 else q[i].k-=res,q2[++p2]=q[i];58 break;59 }60 case 2:{61 if(q[i].id<=mid) add(q[i].l,q[i].k),add(q[i].r+1,-q[i].k),q1[++p1]=q[i];62 else q2[++p2]=q[i];63 break;64 }65 case 3:{66 if(q[i].id<=mid) add(1,q[i].k),add(q[i].r+1,-q[i].k),add(q[i].l,q[i].k),q1[++p1]=q[i];67 else q2[++p2]=q[i];68 break;69 }70 }71 }72 while(top) c[st[top--]]=0;73 for(int i=1;i<=p1;++i) q[l+i-1]=q1[i];74 for(int i=1;i<=p2;++i) q[l+p1+i-1]=q2[i];75 solve(l,l+p1-1,ql,mid),solve(l+p1,r,mid+1,qr);76 }77 int main(){78 // freopen("testdata.in","r",stdin);79 n=read(),m=read();80 for(int i=1;i<=m;++i) a[read()].push_back(i);81 for(int i=1;i<=n;++i) mb[i]=read();82 k=read();83 for(int i=1,l,r,t;i<=k;++i){84 l=read(),r=read(),t=read();85 q[i]=node(l,r,r>=l?2:3,i,t);86 }87 for(int i=1;i<=n;++i)88 q[i+k]=node(0,0,1,i,mb[i]);89 solve(1,k+n,1,k+1);90 for(int i=1;i<=n;++i)91 (ans[i]!=k+1)?printf("%d\n",ans[i]):puts("NIE");92 return 0;93 }