RT，原题：https://loj.ac/p/6279

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int T = 320, L_ = 320, N = 100005;
int blocks, n, size_;
struct block {
	int a[L_], tag, L, R, siz;
	inline int query_max (int c) {
		if (a[1] + tag >= c) return -1e18;
		int w = lower_bound (a + 1, a + 1 + siz, c - tag) - a - 1;
		return a[w] + tag;
	}
} blk[T];
int a[N]; 
struct cut_block {
	int l, r, id, type;
};
inline vector < cut_block > cut (int l, int r) {
	vector < cut_block > res;
	res.clear ();
	for (int i = 1;i <= blocks; ++ i) {
		if (l <= blk[i].L && blk[i].R <= r) {
			cut_block now;
			now.l = blk[i].L;
			now.r = blk[i].R;
			now.id = i;
			now.type = 1;
			res.push_back (now);
		}
		else if (blk[i].L <= l && l <= blk[i].R && blk[i].R <= r) {
			cut_block now;
			now.l = l;
			now.r = blk[i].R;
			now.id = i;
			now.type = 0;
			res.push_back (now);
		}
		else if (l <= blk[i].L && blk[i].L <= r && r <= blk[i].R) {
			cut_block now;
			now.l = blk[i].L;
			now.r = r;
			now.id = i;
			now.type = 0;
			res.push_back (now);
		}
	}
	return res;
}
signed main () {
	scanf ("%lld", &n);
	for (int i = 1;i <= n; ++ i) scanf ("%lld", &a[i]);
	size_ = (int) sqrt (n);
	int L = 1;
	while (true) {
		int R = min (L + size_ - 1, n);
		blocks ++;
		blk[blocks].L = L;
		blk[blocks].R = R;
		blk[blocks].siz = R - L + 1;
		blk[blocks].tag = 0;
		for (int i = L;i <= R; ++ i) blk[blocks].a[i - L + 1] = a[i];
		sort (blk[blocks].a + 1, blk[blocks].a + 1 + (R - L + 1));
		L = R + 1;
		if (L > n) break;
	}
	int q = n;
	while (q --) {
		int op, l, r, c;
		scanf ("%lld %lld %lld %lld", &op, &l, &r, &c);
		if (op == 0) {
			vector < cut_block > res = cut (l, r);
			for (cut_block o : res) {
				if (o.type == 1) blk[o.id].tag += c;
				else {
					for (int i = o.l;i <= o.r; ++ i) a[i] += c;
					for (int i = blk[o.id].L;i <= blk[o.id].R; ++ i) {
						blk[o.id].a[i - blk[o.id].L + 1] = a[i];
					}
					sort (blk[o.id].a + 1, blk[o.id].a + 1 + blk[o.id].siz);
				}
			}
		}
		else {
			int ans = -1e18;
			vector < cut_block > res = cut (l, r);
			for (cut_block o : res) {
				if (o.type == 1) {
					if (blk[o.id].query_max (c) != -1e18) ans = max (ans, blk[o.id].query_max (c));
				}
				else {
					for (int i = o.l;i <= o.r; ++ i) {
						if (a[i] + blk[o.id].tag < c) ans = max (ans, a[i] + blk[o.id].tag);
					}
				}
			}	
			if (ans == -1e18) ans = -1;
			printf ("%lld\n", ans);		
		}
	}
	return 0;
}