是题解里没有的做法。

考虑到字典序是从第一位开始依次往后比较，
对于 $m+1$ 个版本，考虑对于时间轴建立线段树，
若第 $i$ 次操作为 $[l,r]$ 加上 $x$ 的操作则可以转变为了 $[l,r]$ 的版本中 $[i,m]$ 加上了 $x$，这可以差分后推进线段树。

过程是每次保留最小的，但是可能有多个最小值。
反过来考虑，一个版本若不优，则只会被丢一次，所以暴力将大的扔掉即可，时间复杂度 $O(n \log m)$。

const int N = 5e5 + 5;
const ll LNF = 1e18 + 117;
int n, m, a[N];
vector<PII> e[N];
struct SgT {
	int le[N << 2], ri[N << 2];
	ll F[N << 2], G[N << 2], T[N << 2];
	void pushup(int u) {
		F[u] = max(F[u << 1], F[u << 1 | 1]);
		G[u] = min(G[u << 1], G[u << 1 | 1]);
	}
	void push(int u, ll x) {
		F[u] += x, G[u] += x;
		T[u] += x;
	}
	void pushdown(int u) {
		if(T[u]) {
			push(u << 1, T[u]);
			push(u << 1 | 1, T[u]);
			T[u] = 0;
		}
	}
	void build(int u, int l, int r) {
		le[u] = l, ri[u] = r;
		T[u] = 0;
		if(l == r) {
			F[u] = G[u] = 0;
			return;
		}
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
	void modify(int u, int l, int r, int x) {
		if(l <= le[u] && ri[u] <= r) {
			push(u, x);
			return;
		}
		pushdown(u);
		int mid = le[u] + ri[u] >> 1;
		if(l <= mid) modify(u << 1, l, r, x);
		if(mid < r) modify(u << 1 | 1, l, r, x);
		pushup(u);
	}
	void maintain(int u, ll x) {
		if(F[u] <= x) return;
		if(le[u] == ri[u]) {
			G[u] = LNF;
			F[u] = -LNF;
			return;
		}
		pushdown(u);
		maintain(u << 1, x);
		maintain(u << 1 | 1, x);
		pushup(u);
	}
} t;
void solve() {
	cin >> n;
	FOR(i, 1, n) cin >> a[i];
	cin >> m;
	FOR(i, 1, n) e[i].clear();
	FOR(i, 1, m) {
		int l, r, x;
		cin >> l >> r >> x;
		e[l].push_back({i, x});
		e[r + 1].push_back({i, - x});
	}
	t.build(1, 0, m);
	FOR(i, 1, n) {
		for(auto h : e[i])
			t.modify(1, FI(h), m, SE(h));
		cout << t.G[1] + a[i] << " ";
		t.maintain(1, t.G[1]);
	}
	cout << endl;
}