rt，调了一个下午，越改错越多，似乎是 num 的祸，悬赏两关注Orz。

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn = 100000 << 4, maxv = 1e9;
struct node{
	int l, r;
	ll val;
}tree[maxn << 1];
struct query{
    int t, l, r, k, d, s;
}q[maxn];
#define ls(x) (tree[x].l)
#define rs(x) (tree[x].r)
#define val(x) (tree[x].val)
int n, m, a[maxn], b[maxn], id[maxn], c[maxn], cnt = 0, rt[maxn], le[maxn], re[maxn];
int la = 0, ra = 0, k1 = 0, k2 = 0, p = 0, mx = 0;
inline int lbt(int x){return x & (-x);}
void modfiy(int l, int r, ll x, int v, int& i){
	if (!i)i = ++cnt;
	val(i) += v;
	if (l == r)return;
	int mid = l + r >> 1;
	if (x <= mid)modfiy(l, mid, x, v, ls(i));
	else modfiy(mid + 1, r, x, v, rs(i));
}
void upd(int x, ll v){
	int d = lower_bound(b + 1, b + 1 + p, a[x]) - b;
	while(x <= n){
		modfiy(1, p, d, v, c[x]);
        x += lbt(x);
	}
}
ll queryk(int l, int r, int k){
	if (l == r)return l;
	int sum = 0, mid = l + r >> 1;
	for (int i = 1; i <= k2; i++)sum += val(ls(re[i]));
	for (int i = 1; i <= k1; i++)sum -= val(ls(le[i]));
	if (k <= sum){
        for (int i = 1; i <= k1; i++)le[i] = ls(le[i]);
        for (int i = 1; i <= k2; i++)re[i] = ls(re[i]);
        return queryk(l, mid, k);
    }else {
        for (int i = 1; i <= k1; i++)le[i] = rs(le[i]);
        for (int i = 1; i <= k2; i++)re[i] = rs(re[i]);
        return queryk(mid + 1, r, k - sum);
    }
}
ll queryn(int l, int r, int k){
	if (l == r)return 0;
	int sum = 0, mid = l + r >> 1;
	if (k <= mid){
        for (int i = 1; i <= k1; i++)le[i] = ls(le[i]);
        for (int i = 1; i <= k2; i++)re[i] = ls(re[i]);
        return queryn(l, mid, k);
    }else {
    	for (int i = 1; i <= k2; i++)sum += val(ls(re[i])), re[i] = rs(re[i]);
        for (int i = 1; i <= k1; i++)sum -= val(ls(le[i])), le[i] = rs(le[i]);
        return queryn(mid + 1, r, k) + sum;
    }
}
ll build(int l, int r){
	for (int i = 0; i <= 35; i++)le[i] = re[i] = 0;
	la = l - 1, ra = r, k1 = 0, k2 = 0;
	while(la)le[++k1] = c[la], la -= lbt(la);
	while(ra)re[++k2] = c[ra], ra -= lbt(ra);
}
int kth(int l, int r, int k){
	build(l, r);
	return queryk(1, p, k);
}
int num(int l, int r, int k){
	build(l, r);
	return queryn(1, p, k) + 1;
}
int pre(int l, int r, int k){
	int rk = num(l, r, k) - 1;
	if (!rk)return b[0];
	return b[kth(l, r, rk)];
}
int nxt(int l, int r, int k){
	if (k == mx)return b[n + 1];
	int rk = num(l, r, k) + 1;
	if (rk == r - l + 2) return b[n + 1];
	return b[kth(l, r, rk)];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();
	cin >> n >> m;
	char opt; int x, y, z;
	for (int i = 1; i <= n; i++)cin >> a[i], ++a[i], b[++p] = a[i];
    for (int i = 1; i <= m; i++){
        cin >> q[i].t;
        if (q[i].t != 3){
            cin >> q[i].l >> q[i].r >> q[i].k;
            if(q[i].t == 4 || q[i].t == 5)b[++p] = q[i].k;
        }else cin >> q[i].d >> q[i].s, b[++p] = ++q[i].s;
    }
    sort(b + 1, b + p + 1); p = unique(b + 1, b + p + 1) - b - 1;
    b[0] = -2147483647, b[p + 1] = 2147483647;
	for (int i = 1; i <= n; i++)upd(i, 1);
    for (int i = 1; i <= m; i++){
    	if (q[i].t == 1){
    		q[i].k = lower_bound(b + 1, b + n + 1, q[i].k) - b;
    		cout << num(q[i].l, q[i].r, q[i].k) << "\n";
		}
        else if (q[i].t == 2)cout << b[kth(q[i].l, q[i].r, q[i].k)] - 1 << "\n";
        else if(q[i].t == 3){
        	upd(q[i].d, -1);
        	a[q[i].d] = q[i].s;
        	upd(q[i].d, 1);
		}
		else if(q[i].t == 4){
			q[i].k = lower_bound(b + 1, b + n + 1, q[i].k) - b;
			cout << b[pre(q[i].l, q[i].r, q[i].k)] - 1 << "\n";
		}
		else {
			q[i].k = lower_bound(b + 1, b + n + 1, q[i].k) - b;
			cout << b[nxt(q[i].l, q[i].r, q[i].k)] - 1 << "\n";
		}
    }
	return 0;
}