原来TLE36，现在缩减了二分范围满江红，且基本WA online 200+。

出问题的代码：

int l(2e9), r(-2e9);
	for (int k(i + 1); k < j; ++ k)
		l = std::min(l, v[(k - 1) * S + 1].v + Lazy[k]), r = std::max(r, v[k * S].v + Lazy[k]);
	l = std::min(l, std::min(v[L].v + Lazy[i], v[(j - 1) * S + 1].v + Lazy[j]));
	r = std::max(r, std::max(v[i * S].v + Lazy[i], v[R].v + Lazy[j]));

完整code：

#include <cstdio>
#include <cmath>
#include <algorithm>
#define Block(x) ((x - 1) / S + 1)

template<class T, class T2> inline T* upper_bound(T* First, T* Last, T2 val) {
	T * L(First), * R(Last - 1);
	while (L < R) {
		T * mid(L + (R - L >> 1));
		if (val < * mid) R = mid;
		else L = mid + 1;
	}
	return val < (*L) ? L : Last;
}
	
int a[100005], Lazy[100005], n, S;

struct node {
	int v, idx;
	inline void operator = (const node x) {v = x.v, idx = x.idx;}
	inline bool operator < (const node x) const {return v < x.v;}
} v[100005];

inline bool operator < (const int val, const node x) {return val < x.v;}

inline void Sort(const int l, const int r, const int d) {
	int s(Block(l));
	for (int i((s - 1) * S + 1); i <= std::min(s * S, n); ++ i)
		if (l <= v[i].idx && v[i].idx <= r) v[i].v += d, a[v[i].idx] += d;
	std::sort(v + (s - 1) * S + 1, v + std::min(s * S, n) + 1);
}
void update(const int l, const int r, const int d) {
	int i(Block(l)), j(Block(r));
	if (i == j) {Sort(l, r, d); return;}
	for (int k(i + 1); k < j; ++ k) Lazy[k] += d;
	Sort(l, i * S, d); Sort((j - 1) * S + 1, r, d);
}

int query(const int L, const int R, const int K) {
	if (R - L + 1 < K) return -1;
	int i(Block(L)), j(Block(R));
	if (i == j) {
		int b[R - L + 1];
		for (int i(0); i <= R - L; ++ i) b[i] = a[i + L];
		std::sort(b, b + R - L + 1);
		return b[K - 1] + Lazy[i];
	}
	int l(2e9), r(-2e9);
	for (int k(i + 1); k < j; ++ k)
		l = std::min(l, v[(k - 1) * S + 1].v + Lazy[k]), r = std::max(r, v[k * S].v + Lazy[k]);
	l = std::min(l, std::min(v[L].v + Lazy[i], v[(j - 1) * S + 1].v + Lazy[j]));
	r = std::max(r, std::max(v[i * S].v + Lazy[i], v[R].v + Lazy[j]));
	while (l < r) {
		int mid(l + r >> 1), cnt(0);
		for (int k(i + 1); k < j; ++ k)
		cnt += std::upper_bound(v + (k - 1) * S + 1, v + k * S + 1, mid - Lazy[k]) - v - (k - 1) * S - 1;
		for (int k(L); k <= i * S; ++ k)
			if (a[k] + Lazy[i] <= mid) ++ cnt;
		for (int k((j - 1) * S + 1); k <= R; ++ k)
			if (a[k] + Lazy[j] <= mid) ++ cnt;
		if (cnt >= K) r = mid;
		else l = mid + 1;
	}
	return l;
}

int main() {
	int m;
	scanf("%d%d", &n, &m);
	S = sqrt(n);
	for (int i(1); i <= n; ++ i)
		scanf("%d", a + i), v[i].v = a[i], v[i].idx = i;
	for (int i(1); i <= n / S; ++ i)
	std::sort(v + (i - 1) * S + 1, v + i * S + 1);
	std::sort(v + n / S * S + 1, v + n + 1);
	while (m --) {
		int op, l, r, k;
		scanf("%d%d%d%d", &op, &l, &r, &k);
		if (op == 1) printf("%d\n", query(l, r, k));
		else update(l, r, k);
	}
}