如题，但是指针建树。马蜂稍烂。

#include <bits/stdc++.h>

#define rep(i, a, b) for(auto i = (a); i <= (b); i++)
#define _rep(i, a, b) for(auto i = (a); i >= (b); i--)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

template <typename _Tp>
void read(_Tp& first) {
	_Tp x = 0, f = 1; char c = getchar();
	while (!isdigit(c)) {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (isdigit(c)) {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	first = x * f;
}

template <typename _Tp>
void print(_Tp x) {
	if (x < 0) x = (~x + 1), putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

#define int ll
const int MAXN = 5e5 + 5, MAXM = MAXN << 5;

int H[MAXN];
int N;

void init() {
	sort(H + 1, H + 1 + N);
	N = unique(H + 1, H + N + 1) - H - 1;
}

int find(int x) {
	return lower_bound(H + 1, H + 1 + N, x) - H;
}

int n, m, cnt;
int a[MAXN];

struct node {
	node *ls, *rs;
	int sum;

	node() {ls = nullptr, rs = nullptr, sum = 0;}
};

node *root[MAXN];

node *ltr[MAXN], *rtr[MAXN];

#define mid ((L + R) >> 1)

void update(node* &cur, int L, int R, int k, int val) {
	if (!cur) cur = new node();
	if (L == R) return (void) (cur -> sum += val);
	if (k <= mid) update(cur -> ls, L, mid, k, val);
	else update(cur -> rs, mid + 1, R, k, val);
	cur -> sum = 0;
	if (cur -> ls) (cur -> sum) += (cur -> ls -> sum);
	if (cur -> rs) (cur -> sum) += (cur -> rs -> sum);
}

int _kth(int lcnt, int rcnt, int L, int R, int k) {
	if (L == R) return L;
	int x = 0;
	rep (i, 1, rcnt) if (rtr[i] && rtr[i] -> ls) x += rtr[i] -> ls -> sum;
	rep (i, 1, lcnt) if (ltr[i] && ltr[i] -> ls) x -= ltr[i] -> ls -> sum;
	if (k <= x) {
		rep (i, 1, lcnt) if (ltr[i]) ltr[i] = ltr[i] -> ls;
		rep (i, 1, rcnt) if (rtr[i]) rtr[i] = rtr[i] -> ls;
		return _kth(lcnt, rcnt, L, mid, k);
	}
	else {
		rep (i, 1, lcnt) if (ltr[i]) ltr[i] = ltr[i] -> rs;
		rep (i, 1, rcnt) if (rtr[i]) rtr[i] = rtr[i] -> rs;
		return _kth(lcnt, rcnt, mid + 1, R, k - x);
	}
}

int _rnk(int lcnt, int rcnt, int L, int R, int k) {
	if (L == R) return 0;
	int x = 0;
	if (k <= mid) {
		rep (i, 1, lcnt) if (ltr[i]) ltr[i] = ltr[i] -> ls;
		rep (i, 1, rcnt) if (rtr[i]) rtr[i] = rtr[i] -> ls;
		return _rnk(lcnt, rcnt, L, mid, k);
	}
	else {
		rep (i, 1, rcnt) if (rtr[i] && rtr[i] -> ls) x += rtr[i] -> ls -> sum, rtr[i] = rtr[i] -> rs;
		rep (i, 1, lcnt) if (ltr[i] && ltr[i] -> ls) x -= ltr[i] -> ls -> sum, ltr[i] = ltr[i] -> rs;
		return x + _rnk(lcnt, rcnt, mid + 1, R, k);
	}
}

int lowbit(int x) {
	return x & -x;
}

void add(int x, int val) {
	if (!x) return;
	int tx = x;
	while (x <= n) {
		update(root[x], 1, N, a[tx], val), x += lowbit(x);
	}
}

int kth(int L, int R, int k) {
	int lcnt = 0, rcnt = 0;
	--L;
	while (R) (root[R] == nullptr ? 0 : rtr[++rcnt] = root[R]), R -= lowbit(R);
	while (L) (root[L] == nullptr ? 0 : ltr[++lcnt] = root[L]), L -= lowbit(L);
	return _kth(lcnt, rcnt, 1, N, k);
}

int rnk(int L, int R, int k) {
	int lcnt = 0, rcnt = 0;
	--L;
	while (R) (root[R] == nullptr ? 0 : rtr[++rcnt] = root[R]), R -= lowbit(R);
	while (L) (root[L] == nullptr ? 0 : ltr[++lcnt] = root[L]), L -= lowbit(L);
	return _rnk(lcnt, rcnt, 1, N, k) + 1;
}

int prev(int L, int R, int k) {
	int rk = rnk(L, R, k) - 1;
	if (rk == 0) return 0;
	else return kth(L, R, rk);
}

int nxt(int L, int R, int k) {
	if (k >= N) return N + 1;
	int rk = rnk(L, R, k + 1);
	if (rk > R - L + 1) return N + 1;
	return kth(L, R, rk);
}

struct ops {
	int op, l, r, pos, k;
} op[MAXN];

signed main() {
	read(n), read(m);
	rep (i, 1, n) {
		read(a[i]);
		H[++N] = a[i];
	}
	rep (i, 1, m) {
		read(op[i].op);
		if (op[i].op == 1) read(op[i].l), read(op[i].r), read(op[i].k), H[++N] = op[i].k;
		if (op[i].op == 2) read(op[i].l), read(op[i].r), read(op[i].k);
		if (op[i].op == 3) read(op[i].pos), read(op[i].k), H[++N] = op[i].k;
		if (op[i].op == 4) read(op[i].l), read(op[i].r), read(op[i].k), H[++N] = op[i].k;
		if (op[i].op == 5) read(op[i].l), read(op[i].r), read(op[i].k), H[++N] = op[i].k;

	}
	init();
	H[0] = (-2147483647);
	H[N + 1] = (2147483647);
	rep (i, 1, n) a[i] = find(a[i]), add(i, 1);
	rep (i, 1, m) {
		int op, l, r, pos, k;
		op = ::op[i].op;
		switch (op) {
			case 1:
				l = ::op[i].l, r = ::op[i].r, k = ::op[i].k;
				print(rnk(l, r, find(k))), putchar(10);
				break;
			case 2:
				l = ::op[i].l, r = ::op[i].r, k = ::op[i].k;
				print(H[kth(l, r, k)]), putchar(10);
				break;
			case 3:
				pos = ::op[i].pos, k = ::op[i].k;
				add(pos, -1);
				a[pos] = find(k);
				add(pos, 1);
				break;
			case 4:
				l = ::op[i].l, r = ::op[i].r, k = ::op[i].k;
				print(H[prev(l, r, k)]), putchar(10);
				break;
			case 5:
				l = ::op[i].l, r = ::op[i].r, k = ::op[i].k;
				print(H[nxt(l, r, k)]), putchar(10);
				break;
		}
	}
	return 0;
}

样例已过，30pts 调 9+ 小时无果。

AC #2, #9, #10。