全局二分+树状数组，其实还是比较水。
比较坑的一点是直接求和会暴long long。如果≥Pi了要直接break掉。好坑啊。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
int _d_;
#define readInt(_x_) { \
int& _s_ = (_x_ = 0); \
while (!isdigit(_d_ = getchar())); \
while (_s_ = (_s_ << 3) + (_s_ << 1) + _d_ - 48, isdigit(_d_ = getchar())); \
}
typedef long long dint;
const int maxn = 300009;
struct node {
int v;
node *next;
};
struct rain {
int l, r, a;
};
struct bintree {
dint t[maxn];
int n;
bintree() {
memset(t, 0, sizeof(t));
}
void chg(int p, int v) {
for (; p <= n; p += (p & -p))
t[p] += v;
}
dint qry(int p) {
dint s = 0;
for (; p; p -= (p & -p))
s += t[p];
return s;
}
};
int n, m, t, ans[maxn], o[maxn], w[maxn];
bool dr[maxn];
rain a[maxn];
node *head[maxn], *np;
bintree bt;
void binTest(int vl, int vr, int ql, int qr) {
if (ql >= qr)
return;
else if (vl + 1 == vr) {
for (int i = ql; i < qr; ++ i)
ans[o[i]] = vl;
}
else {
int vm = (vl + vr) >> 1;
for (int i = vl; i < vm; ++ i)
if (a[i]. l <= a[i]. r) {
bt. chg(a[i]. l, a[i]. a);
bt. chg(a[i]. r + 1, -a[i]. a);
}
else {
bt. chg(1, a[i]. a);
bt. chg(a[i]. r + 1, -a[i]. a);
bt. chg(a[i]. l, a[i]. a);
}
for (int i = ql; i < qr; ++ i) {
dint sc = 0;
for (node* j = head[o[i]]; j && sc < w[o[i]]; j = j-> next)
sc += bt. qry(j-> v);
if (sc >= w[o[i]])
dr[i] = 0;
else
dr[i] = 1;
}
int nl = ql, nr = qr - 1;
while (nl <= nr) {
for (; nl < nr && !dr[nl]; ++ nl);
for (; nl < nr && dr[nr]; -- nr);
if (nl <= nr) {
swap(o[nl], o[nr]);
swap(dr[nl], dr[nr]);
++ nl;
-- nr;
}
}
for (nl = ql; nl < qr && !dr[nl]; ++ nl);
binTest(vm, vr, nl, qr);
for (int i = vl; i < vm; ++ i)
if (a[i]. l <= a[i]. r) {
bt. chg(a[i]. l, -a[i]. a);
bt. chg(a[i]. r + 1, a[i]. a);
}
else {
bt. chg(1, -a[i]. a);
bt. chg(a[i]. r + 1, a[i]. a);
bt. chg(a[i]. l, -a[i]. a);
}
binTest(vl, vm, ql, nl);
}
}
int main() {
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif
readInt(n);
readInt(m);
bt. n = m + 1;
memset(head, 0, sizeof(head));
np = new node[m];
for (int i = 1; i <= m; ++ i) {
int v;
readInt(v);
np-> v = i;
np-> next = head[v];
head[v] = np ++;
}
for (int i = 1; i <= n; ++ i) {
readInt(w[i]);
o[i - 1] = i;
}
readInt(t);
for (int i = 0; i < t; ++ i) {
readInt(a[i]. l);
readInt(a[i]. r);
readInt(a[i]. a);
}
a[t]. l = a[t]. r = 1;
a[t]. a = 0;
binTest(0, t + 1, 0, n);
for (int i = 1; i <= n; ++ i)
if (ans[i] == t)
puts("NIE");
else
printf("%d\n", ans[i] + 1);
}