求区间内右边的数减左边的数的最大值（线段树）

作者：XiaoQuQu，发表于 Sun Jul 07 2024。

大致思想就是先求出每个区间的 max, min，然后一个区间内的右边的数减左边的数可以分为 左右两边的右减左最大值 或 右子树减左子树的最大值 两种情况。

所以对于每个节点维护一下 mx, mn, rml 三个值，其中 rml 表示当前节点的最大右减左，就做完了。

struct _sgt {	
	struct _node {
		int sm, mn, mx, rml, tg;
	} tr[MAXN << 2];

	void pushup(int p) {
		tr[p].sm = tr[lson].sm + tr[rson].sm;
		tr[p].mn = min(tr[lson].mn, tr[rson].mn);
		tr[p].mx = max(tr[lson].mx, tr[rson].mx);
		tr[p].rml = max(max(tr[lson].rml, tr[rson].rml), tr[rson].mx - tr[lson].mn);
	}
	
	void addtag(int p, int v, int l, int r) {
		tr[p].tg += v;
		tr[p].mn += v;
		tr[p].mx += v;
		tr[p].sm += (r - l + 1) * v;
	}
	
	void pushdown(int p, int l, int r) {
		if (!tr[p].tg) return;
		addtag(lson, tr[p].tg, l, mid);
		addtag(rson, tr[p].tg, mid + 1, r);
		tr[p].tg = 0;
	}
	
	void update(int p, int l, int r, int L, int R, int v) {
		if (L <= l && r <= R) return addtag(p, v, l, r);
		pushdown(p, l, r);
		if (L <= mid) update(lson, l, mid, L, R, v);
		if (mid < R) update(rson, mid + 1, r, L, R, v);
		pushup(p);
	}
	
	int query(int p, int l, int r, int L, int R) {
		if (L <= l && r <= R) return tr[p].sm;
		int ret = 0;
		pushdown(p, l, r);
		if (L <= mid) ret += query(lson, l, mid, L, R);
		if (mid < R) ret += query(rson, mid + 1, r, L, R);
		return ret;
	}
	
	int queryMin(int p, int l, int r, int L, int R) {
		if (L <= l && r <= R) return tr[p].mn;
		int ret = INT_MAX;
		pushdown(p, l, r);
		if (L <= mid) ret = min(ret, queryMin(lson, l, mid, L, R));
		if (mid < R) ret = min(ret, queryMin(rson, mid + 1, r, L, R));
		return ret;
	}
	
	int queryMax(int p, int l, int r, int L, int R) {
		if (L <= l && r <= R) return tr[p].mx;
		int ret = INT_MIN;
		pushdown(p, l, r);
		if (L <= mid) ret = max(ret, queryMax(lson, l, mid, L, R));
		if (mid < R) ret = max(ret, queryMax(rson, mid + 1, r, L, R));
		return ret;
	}
	
	int queryRML(int p, int l, int r, int L, int R) {
		if (L <= l && r <= R) return tr[p].rml;
		int ret = INT_MIN;
		pushdown(p, l, r);
		if (L <= mid) ret = max(ret, queryRML(lson, l, mid, L, R));
		if (mid < R) ret = max(ret, queryRML(rson, mid + 1, r, L, R));
		if (L <= mid && mid < R) {
			ret = max(ret, queryMax(rson, mid + 1, r, L, R) - queryMin(lson, l, mid, L, R));
		}
		return ret;
	}
} s;