整体二分加差分

#include <bits/stdc++.h>
#define N 600005
#define ll unsigned long long 
using namespace std;

inline int read() {
	int res = 0; char c = getchar();
	while (c < '0' || c > '9') { c = getchar(); }
	while (c >= '0' && c <= '9') { res = (res << 1) + (res << 3) + (c ^ 48); c = getchar(); }
	return res;
}
int n, m, k, q[N], ans[N], qu[N], tot, len, tmp[N];
ll cnt[N], c[N], be[N], p[N];
struct rain {
	int l, r;
	ll a;
} ra[N];

inline void solve(int l, int r, int ql, int qr) {
	if (ql > qr) return ;
	if (l == r) {
//		cout << l << ' ' << ql << ' ' << qr << '\n';
		for (int i = ql; i <= qr; ++i) ans[qu[i]] = l;
		return ;
	}
	int mid = (l + r) >> 1;
	for (int i = 1; i <= mid; ++i) {
		if (ra[i].l > ra[i].r) {
			c[ra[i].l] += ra[i].a;
			c[1] += ra[i].a;
			c[ra[i].r + 1] -= ra[i].a;
		}
		else {
			c[ra[i].l] += ra[i].a;
			c[ra[i].r + 1] -= ra[i].a;
		}
	}
	
	for (int i = 1; i <= m; ++i) cnt[be[i]] += (c[i] += c[i - 1]);
	for (int i = 0; i <= m; ++i) c[i] = 0;
	
	
	int qr1;
	len = ql - 1;
	
	for (int i = ql; i <= qr; ++i) 
		if (cnt[qu[i]] >= p[qu[i]]) tmp[++len] = qu[i];
	qr1 = len;
	
	for (int i = ql; i <= qr; ++i) 
		if (cnt[qu[i]] < p[qu[i]]) tmp[++len] = qu[i];
	for (int i = ql; i <= qr; ++i) qu[i] = tmp[i];
	// cout << ql1 << ' ' << qr1 << ' ' << ql2 << ' ' << qr2 << '\n';
//	for (int i = 1; i <= m; ++i) cnt[be[i]] = 0;
	for (int i = 1; i <= n; ++i) cnt[i] = 0;
	solve(l, mid, ql, qr1);
	solve(mid + 1, r, qr1 + 1, qr);
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= m; ++i) be[i] = read();
	for (int i = 1; i <= n; ++i) p[i] = read();
	k = read();
	for (int i = 1; i <= k; ++i) {
		int l = read(), r = read();
		ll a = read();
		ra[i] = { l, r, a };
	}
	for (int i = 1; i <= n; ++i) qu[++tot] = i;
//	tot = n;
	solve(1, k + 1, 1, n);
	for (int i = 1; i <= n; ++i) 
		if (ans[i] != k + 1)
			cout << ans[i] << '\n';
		else cout << "NIE\n";
	return 0;
}