题解：P14255 列车（train）

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int L[N << 2], R[N << 2], tag[N << 2], mx[N << 2], mn[N << 2], P[N], n, q, pre, T;

inline void cov(int u, int v) {
	tag[u] = mx[u] = v, mn[u] = P[v] - P[R[u]];
}

inline void down(int u) {
	if (~tag[u])
		if (L[u]^R[u])
			cov(u * 2, tag[u]), cov(u * 2 + 1, tag[u]), tag[u] = -1;
}

inline void up(int u) {
	if (L[u]^R[u])
		mx[u] = max(mx[u * 2], mx[u * 2 + 1]), mn[u] = min(mn[u * 2], mn[u * 2 + 1]);
}

void build(int l, int r, int p) {
	L[p] = l, R[p] = r, tag[p] = -1, mx[p] = r + 1;
	int m = (l + r) / 2;
	if (l ^ r)
		build(l, m, p * 2), build(m + 1, r, p * 2 + 1), up(p);
	else
		mn[p] = P[r + 1] - P[l];
}

void modi(int l, int r, int p, int v) {
	if (l <= L[p] && r >= R[p])
		return cov(p, v);
	if (l > R[p] || r < L[p])
		return;
	down(p), modi(l, r, p * 2, v), modi(l, r, p * 2 + 1, v), up(p);
}

int que(int p, int v) {
	if (L[p] == R[p])
		return L[p];
	down(p);
	if (mx[p * 2] > v)
		return que(p * 2, v);
	else
		return que(p * 2 + 1, v);
}

int qmn(int l, int r, int p) {
	if (l <= L[p] && r >= R[p])
		return mn[p];
	if (l > R[p] || r < L[p])
		return 0x3f3f3f3f;
	down(p);
	return min(qmn(l, r, p * 2), qmn(l, r, p * 2 + 1));
}

void solve() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> P[i];
	P[n + 1] = 0x7f7f7f7f, build(1, n + 1, 1), pre = 1;
	while (q--) {
		int op, l, r, p;
		cin >> op >> l >> r;
		if (op == 1) {
			p = que(1, r);
			if (p > l)
				modi(l, p - 1, 1, r + 1);
			if (l == 1 && r == n)
				pre = 0;
		} else {
			if (!pre) {
				cout << "-1\n";
				continue;
			}
			p = que(1, r);
			int res = 0x3f3f3f3f;
			if (p ^ 1)
				res = P[r] - P[min(p - 1, l)]; //to r
			if (p <= l)
				res = min(res, qmn(p, l, 1)); //further
			cout << res << '\n';
		}
	}
}

main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--)
		solve();
}