Gerw学长讲的整体二分模板
//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
const int maxn=3e5+5;
using namespace std;
typedef long long LL;
int n,m,kk,z[maxn],qw[maxn],l[maxn],r[maxn],v[maxn],now,ans[maxn];
int ecnt,fir[maxn],nxt[maxn],to[maxn],que[maxn],tp[maxn];
LL sum[maxn];//注意开LL.....
inline int read(){
char ch=getchar(); int res=0,f=1;
while((ch!='-')&&(ch>'9'||ch<'0')) ch=getchar();
if(ch=='-') f=-1,ch=getchar();
for(;ch>='0'&&ch<='9';ch=getchar()) res=res*10+ch-'0';
return res*f;
}
void jiabian(int x,int y) {nxt[++ecnt]=fir[x];fir[x]=ecnt;to[ecnt]=y;}
void add(int x,LL y) {for(int i=x;i<=m;i+=(i&(-i))) sum[i]+=y;}
LL qry(int x) {LL res=0; for(int i=x;i>0;i-=(i&(-i))) res+=sum[i]; return res;}
void ADD(int l,int r,LL y){
if(l<=r) {add(l,y);add(r+1,-y);}
else {add(1,y);add(r+1,-y),add(l,y);}
}
void solve(int ll,int rr,int ql,int qr){
if(ql>qr) return;
if(ll==rr){
for(int i=ql;i<=qr;i++)
ans[que[i]]=ll;
return;
}
int mid=ll+((rr-ll)>>1);
while(now<mid) {
now++;
ADD(l[now],r[now],(LL)v[now]);}
while(now>mid)
{ADD(l[now],r[now],-(LL)v[now]);
now--;
}
int aa=ql,bb=qr;
for(int i=ql;i<=qr;i++){ //这一段里注意所有的que[i]不是i
LL as=0;
for(int j=fir[que[i]];j;j=nxt[j])
{as+=qry(j);
if(as>=qw[que[i]]) break;
}
if(as>=qw[que[i]]) tp[aa++]=que[i];
else tp[bb--]=que[i];
}
for(int i=ql;i<=qr;i++)
que[i]=tp[i];
solve(ll,mid,ql,aa-1);
solve(mid+1,rr,aa,qr);
}
int main()
{
n=read(); m=read();
for(int i=1;i<=m;i++) { z[i]=read(); jiabian(z[i],i); }
for(int i=1;i<=n;i++) { qw[i]=read();que[i]=i;}
kk=read();
for(int i=1;i<=kk;i++) {l[i]=read(); r[i]=read(); v[i]=read();}
kk++; l[kk]=1; r[kk]=m; v[kk]=1e9+7;
solve(1,kk,1,n);
for(int i=1;i<=n;i++) {
if(ans[i]<kk) printf("%d
",ans[i]);
else printf("NIE
");
}
return 0;
}