哪里复杂度假了啊，TLE 的点要跑四十几秒

提交记录

# include <bits/stdc++.h>
using namespace std;

const int maxn = 300005;

struct reader {
	template <typename Type>
	reader & operator >> (Type & ret) {
		int f = 1; ret = 0; char ch = getchar ();
		for (;!isdigit (ch); ch = getchar ()) if (ch == '-') f = -f;
		for (; isdigit (ch); ch = getchar ()) ret = (ret * 10) + (ch - '0');
		ret *= f; return * this;
	}
} fin;

int n, m, k;
vector < int > a[maxn]; unsigned long long c[maxn], b[maxn];
int ll[maxn], rr[maxn], p[maxn], id[maxn], nxt[maxn], res[maxn];

long long T[maxn];
long long query (int id) {
	long long ret = 0;
	for (; id >= 1; id -= id & -id) ret += T[id];
	return ret;
}
void update (int id, long long num) {
	for (; id <= m; id += id & -id) T[id] += num;
	return ;
}

void solve (int l, int r, int L, int R) {
	if (l == r) { for (int i = L; i <= R; i++) res[id[i]] = l; return ; }
	int mid = (l + r) >> 1, l_ = L - 1, r_ = R + 1;
	for (int i = 1; i <= mid; i++) {
		update (ll[i], c[i]), update (rr[i] + 1, -c[i]);
		if (ll[i] > rr[i]) update (1, c[i]);
	}
	for (int i = L; i <= R; i++) {
		unsigned long long now = 0;
		for (int j : a[id[i]]) now += query (j);
		if (b[id[i]] <= now) nxt[++l_] = id[i];
		else nxt[--r_] = id[i];
	}
	for (int i = 1; i <= mid; i++) {
		update (ll[i], -c[i]), update (rr[i] + 1, c[i]);
		if (ll[i] > rr[i]) update (1, -c[i]);
	}
	for (int i = L; i <= R; i++) swap (id[i], nxt[i]);
	if (L <= l_) solve (l, mid, L, l_); if (r_ <= R) solve (mid + 1, r, r_, R);
	for (int i = L; i <= R; i++) swap (id[i], nxt[i]);
	return ;
}

int main () {
	freopen ("2.in", "r", stdin);
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		fin >> p[i]; a[p[i]].push_back (i);
	}
	for (int i = 1; i <= n; i++) fin >> b[i], b[0] = max (b[0], b[i]), id[i] = i;
	fin >> k;
	for (int i = 1; i <= k; i++) fin >> ll[i] >> rr[i] >> c[i];
	ll[k + 1] = 1; rr[k + 1] = m; c[k + 1] = b[0];
	solve (1, k + 1, 1, n);
	for (int i = 1; i <= n; i++) {
		if (res[i] == k + 1) puts ("NIE");
		else printf ("%d\n", res[i]);
	}
	return 0;
}