[3r -- 5r] 视速度而定 /kel

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;

const int N = 5e4 + 5, inf = INT_MAX;
int n, Q, a[N];

namespace FhqTreap {
	struct Tree {
		int ls, rs;
		int val, pri, siz;
	} t[N * 40];		
	int tot;
	int Create(int x) {
		t[++tot] = {0, 0, x, rand(), 1};
		return tot;
	}
	void Pushup(int pos) { t[pos].siz = t[t[pos].ls].siz + t[t[pos].rs].siz + 1; }
	void Split(int pos, int &x, int &y, int k) {
		if (!pos) {
			x = y = 0;
			return;
		}
		if (t[pos].val <= k) x = pos, Split(t[pos].rs, t[pos].rs, y, k);
		else y = pos, Split(t[pos].ls, x, t[pos].ls, k);
		Pushup(pos);
	}
	int Merge(int x, int y) {
		if (!x || !y) return x + y;
		if (t[x].pri > t[y].pri) {
			t[x].rs = Merge(t[x].rs, y);
			Pushup(x); return x;
		}
		else {
			t[y].ls = Merge(x, t[y].ls);
			Pushup(y); return y;
		}
	}
	void Insert(int &root, int k) {
		int x, y; Split(root, x, y, k);
		root = Merge(x, Merge(Create(k), y));
	}
	void Delete(int &root, int k) {
		int x, y, z; Split(root, x, z, k); Split(x, x, y, k - 1);
		y = Merge(t[y].ls, t[y].rs); root = Merge(x, Merge(y, z));
	}
	int Rank(int &root, int k) {
		int x, y; Split(root, x, y, k - 1);
		int ans = t[x].siz; root = Merge(x, y); return ans;
	}
	int Kth(int pos, int k) {
		int lsiz = t[t[pos].ls].siz;
		if (lsiz + 1 == k) return t[pos].val;
		else if (lsiz + 1 < k) return Kth(t[pos].rs, k - (lsiz + 1));
		else return Kth(t[pos].ls, k);
	}
	int Pre(int &root, int k) {
		int x, y; Split(root, x, y, k);
		if (!x) return -inf;
		int ans = Kth(x, t[x].siz); root = Merge(x, y); return ans;
	}
	int Suf(int &root, int k) {
		int x, y; Split(root, x, y, k);
		if (!y) return inf;
		int ans = Kth(y, 1); root = Merge(x, y); return ans;
	}
} using namespace FhqTreap;

namespace SegmentTree {
#define ls (pos << 1)
#define rs (pos << 1 | 1)
	struct Seg {
		int l, r;
		int root;
	} s[N << 2];
#define mid ((s[pos].l + s[pos].r) >> 1)
	void build(int pos, int l, int r) {
		s[pos].l = l, s[pos].r = r;
		if (l == r) {
			s[pos].root = Create(a[mid]);
			return;
		}
		for (int i = l; i <= r; i++) Insert(s[pos].root, a[i]);
		build(ls, l, mid); build(rs, mid + 1, r);
	}
	void update(int pos, int id, int k) {
		Delete(s[pos].root, a[id]); Insert(s[pos].root, k);
		if (s[pos].l == s[pos].r) return;
		id <= mid ? update(ls, id, k) : update(rs, id, k);
	}
	int rnk(int pos, int l, int r, int k) {
		if (l <= s[pos].l && s[pos].r <= r) return Rank(s[pos].root, k);
		return (l <= mid ? rnk(ls, l, r, k) : 0) + (r > mid ? rnk(rs, l, r, k) : 0);
	}
	int kth(int qwq, int l, int r, int k){
		int L = 0, R = 1e8, ans = 0;
		for (int Mid; Mid = (L + R) >> 1, L <= R; )
			if (rnk(1, l, r, Mid) + 1 <= k) ans = Mid, L = Mid + 1;
			else R = Mid - 1;
		return ans;
	}
	int pre(int pos, int l, int r, int k) {
		if (l <= s[pos].l && s[pos].r <= r) return Pre(s[pos].root, k);
		return max((l <= mid ? pre(ls, l, r, k) : -inf), (r > mid ? pre(rs, l, r, k) : -inf));
	}
	int suf(int pos, int l, int r, int k) {
		if (l <= s[pos].l && s[pos].r <= r) return Suf(s[pos].root, k);
		return min((l <= mid ? suf(ls, l, r, k) : inf), (r > mid ? suf(rs, l, r, k) : inf));
	}
} using namespace SegmentTree;

signed main() {
	srand(time(nullptr));
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> Q; for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n);
	for (int opt, x, y, k; Q--; ) {
		cin >> opt >> x >> y;
		if (opt == 3) update(1, x, y), a[x] = y;
		else {
			cin >> k;
			if (opt == 1) cout << rnk(1, x, y, k) + 1 << '\n';
			if (opt == 2) cout << kth(1, x, y, k) << '\n';
			if (opt == 4) cout << pre(1, x, y, k) << '\n';
			if (opt == 5) cout << suf(1, x, y, k) << '\n';
		}
	}
	return 0;
}