SCP-S2025 T3求助

#include <bits/stdc++.h>
#define int long long
#define INF 1145141919810ll
#define mid (l+r)/2ll
using namespace std;
int T, n, m;
int a[114514];

struct node {
	int pre, bac;
};

struct Segment_Tree {
	int pre[16 * 114514], bac[16 * 114514];
	node tag[16 * 114514];
	void build(int l, int r, int p) {
		tag[p] = (node) {
			INF, -INF
		};
		if (l >= r) {
			pre[p] = a[r - 1];
			bac[p] = a[r + 1];
			return ;
		}
		build(l, mid, p * 2);
		build(mid + 1, r, p * 2 + 1);
		pushup(l, r, p);
		return ;
	}
	void pushup(int l, int r, int p) {
		pre[p] = max(pre[p * 2], pre[p * 2 + 1]);
		bac[p] = min(bac[p * 2], bac[p * 2 + 1]);
	}
	void maketag(int l, int r, int p, node k) {
		if (k.pre < pre[p]) {
			pre[p] = k.pre;
			tag[p].pre = k.pre;
		}
		if (k.bac > bac[p]) {
			bac[p] = k.bac;
			tag[p].bac = k.bac;
		}
	}
	void pushdown(int l, int r, int p) {
		maketag(l, mid, p * 2, tag[p]);
		maketag(mid + 1, r, p * 2 + 1, tag[p]);
	}
	void update(int wl, int wr, int l, int r, int p, node k) {
		if (l > wr || r < wl) {
			return ;
		}
		if (wl <= l && r <= wr) {
			maketag(l, r, p, k);
			return ;
		}
		pushdown(l, r, p);
		update(wl, wr, l, mid, p * 2, k);
		update(wl, wr, mid + 1, r, p * 2 + 1, k);
		return ;
	}
	node query(int wp, int l, int r, int p) {
		if (l >= r && r == wp) {
			return (node) {
				pre[p], bac[p]
			};
		}
		pushdown(l, r, p);
		pushup(l, r, p);
		if (mid < wp) {
			return query(wp, mid + 1, r, p * 2 + 1);
		} else {
			return query(wp, l, mid, p * 2);
		}
	}
} seg;

signed main() {
//	freopen("train.in", "r", stdin);
//	freopen("train.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;
	while (T--) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		a[n + 1] = INF;
		a[0] = -INF;
		seg.build(1, n, 1);
		int O, X, Y, ans = INF;
		for (int i = 1; i <= m; i++) {
//			for (int i = 1; i <= n; i++) {
//				cout << seg.query(i, 1, n, 1).pre << ' ' << seg.query(i, 1, n, 1).bac << '\n';
//			}
			ans = INF;
			cin >> O >> X >> Y;
			if (O == 1) {
				seg.update(X, Y, 1, n, 1, (node) {
					a[X - 1], a[Y + 1]
				});
			} else if (O == 2) {
				ans = min(ans, max(a[Y], seg.query(X, 1, n, 1).bac) - a[X]);
				ans = min(ans, a[Y] - min(a[X], seg.query(Y, 1, n, 1).pre));
				if (ans > 10000000000ll || ans < -10000000000ll) {
					cout << -1 << '\n';
				} else {
					cout << ans << '\n';
				}
			}
		}
	}
	return 0;
}