https://www.luogu.com.cn/record/94210690

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 5, K = 1e8;
int n, q, l, r, k, d, cnt, a[N], sum[N], Ls[N], Rs[N], T[N];
char opt;
inline int ls(int p) { return Ls[p] ? Ls[p] : Ls[p] = ++ cnt; }
inline int rs(int p) { return Rs[p] ? Rs[p] : Rs[p] = ++ cnt; }
inline int Rt(int p) { return T[p] ? T[p] : T[p] = ++ cnt; }
void modify(int p, int l, int r, int t, int k) {
	sum[p] += k;
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (t <= mid) modify(ls(p), l, mid, t, k);
	else modify(rs(p), mid + 1, r, t, k);
}
int query(int p, int l, int r, int nl, int nr) {
	if (nl <= l && r <= nr) return sum[p];
	int mid = (l + r) >> 1, res = 0;
	if (nl <= mid) res += query(ls(p), l, mid, nl, nr);
	if (nr > mid) res += query(rs(p), mid + 1, r, nl, nr);
	return res;
}
void Modify(int p, int l, int r, int t, int k, int v) {
	modify(Rt(p), 1, n, t, v);
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (k <= mid) Modify(ls(p), l, mid, t, k, v);
	else Modify(rs(p), mid + 1, r, t, k, v);
}
int Query(int p, int l, int r, int pl, int pr, int nl, int nr) {
	if (nl <= l && r <= nr) return query(Rt(p), 1, n, pl, pr);
	int mid = (l + r) >> 1, res = 0;
	if (nl <= mid) res += Query(ls(p), l, mid, pl, pr, nl, nr);
	if (nr > mid) res += Query(rs(p), mid + 1, r, pl, pr, nl, nr);
	return res;
}
int Kth(int p, int l, int r, int nl, int nr, int k) {
	if (l == r) return l;
	int mid = (l + r) >> 1, v = query(Rt(ls(p)), 1, n, nl, nr);
	if (v >= k) return Kth(ls(p), l, mid, nl, nr, k);
	else return Kth(rs(p), mid + 1, r, nl, nr, k - v);
}
int main() {
//    ios::sync_with_stdio(0);
//    cin.tie(0), cout.tie(0);
	cin >> n >> q, cnt = 1;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], a[i] += 2, Modify(1, 1, K, i, a[i], 1);
	for (int i = 1; i <= q; i ++) {
		cin >> opt;
		if (opt == '1') cin >> l >> r >> k, k += 2, cout << Query(1, 1, K, l, r, 1, k - 1) + 1 << '\n';
		if (opt == '2') cin >> l >> r >> k, cout << Kth(1, 1, K, l, r, k) - 2 << '\n';
		if (opt == '3') cin >> l >> k, k += 2, Modify(1, 1, K, l, a[l], -1), a[l] = k, Modify(1, 1, K, l, k, 1); 
		if (opt == '4') {
			cin >> l >> r >> k, k += 2;
			int v = Query(1, 1, K, l, r, 1, k - 1);
			if (1 <= v) cout << Kth(1, 1, K, l, r, v) - 2 << '\n';
			else puts("-2147483647");
		}
		if (opt == '5') {
			cin >> l >> r >> k, k += 2;
			int v = Query(1, 1, K, l, r, 1, k) + 1;
			if (v <= query(Rt(1), 1, n, l, r)) cout << Kth(1, 1, K, l, r, v) - 2 << '\n';
			else puts("2147483647");
		}
	}
	return 0;
}