```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k,x,y,z,flag,head,ans[300039],sx[300039],sy[300039],sz[300039],cur;
long long sum[300039],tot;
struct ques {
int l,r,mid,num;long long p;
} f[300039];
inline bool cmp(ques x,ques y) {return x.mid<y.mid;}
struct yyy {int to,z;} tmp;
struct ljb {
int head,h[300039];
yyy f[600039];
inline void add(int x,int y) {
f[++head]=(yyy) {y,h[x]};
h[x]=head;
}
} s;
inline void get(int x,int y) {while(x<=m)sum[x]+=y,x+=x&-x;}
inline long long find(int x) {long long ans=0;while(x)ans+=sum[x],x-=x&-x;return ans;}
int main() {
//freopen("1.in","r",stdin);
memset(s.h,-1,sizeof(s.h));
register int i;
scanf("%d%d",&n,&m);
for(i=1; i<=m; i++) {
scanf("%d",&x);
s.add(x,i);
}
for(i=1; i<=n; i++) scanf("%d",&f[i].p);
scanf("%d",&k);
for(i=1; i<=n; i++) f[i].r=k+1,f[i].mid=k+1>>1,f[i].num=i;
for(i=1; i<=k; i++) scanf("%d%d%d",&sx[i],&sy[i],&sz[i]);
while(1) {
flag=0;
for(i=1; i<=n; i++) if(f[i].l+1<f[i].r) {flag=1;break;}
if(!flag) break;
sort(f+1,f+n+1,cmp);
head=0;
memset(sum,0,sizeof(sum));
for(i=1; i<=n; i++) {
if(f[i].l+1<f[i].r) {
while(head!=k&&head<f[i].mid) {
head++;
if(sx[head]<sy[head]) get(sx[head],sz[head]),get(sy[head]+1,-sz[head]);
else get(sx[head],sz[head]),get(sy[head]+1,-sz[head]),get(1,sz[head]);
}
tot=0;
cur=s.h[f[i].num];
while(cur!=-1) {
tmp=s.f[cur];
tot+=find(tmp.to);
if(tot>=f[i].p) break;
cur=tmp.z;
}
if(tot<f[i].p) f[i].l=f[i].mid;
else f[i].r=f[i].mid;
f[i].mid=f[i].l+f[i].r>>1;
}
}
}
for(i=1; i<=n; i++) ans[f[i].num]=f[i].r;
for(i=1; i<=n; i++) {
if(ans[i]==k+1) printf("NIE\n");
else printf("%d\n",ans[i]);
}
}
```
by 275307894a @ 2020-08-15 15:41:56
qndmx
by wgyhm @ 2020-08-15 15:47:36
好吧少了个等号
by 275307894a @ 2020-08-15 15:49:24
此贴终结
by 275307894a @ 2020-08-15 15:49:32