RT，估计是求排名写挂了，但我没有证据

#include<bits/stdc++.h>
#define int long long
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mid (l + r >> 1)
using namespace std;
int n, m;
struct node {
	int val[4000005], rd[4000005];
	int size[4000005], son[4000005][2];
	int sum, x, y, z;
	void pushup(int k) {size[k] = size[son[k][0]] + size[son[k][1]] + 1;}
	int new_node(int v) {
		sum++;
		val[sum] = v; rd[sum] = rand(); size[sum] = 1;
		return sum;
	} 
	void split(int k, int v, int &x, int &y) {
		if (!k) {x = y = 0; return;}
		if (val[k] <= v)
		    x = k, split(son[k][1], v, son[k][1], y);
		else
		    y = k, split(son[k][0], v, x, son[k][0]);
		pushup(k);
	}
	int merge(int x, int y) {
		if (!x || !y) return x + y;
		if (rd[x] < rd[y]) {
			son[x][1] = merge(son[x][1], y); pushup(x);
			return x;
		} else {
			son[y][0] = merge(x, son[y][0]); pushup(y);
			return y;
		}
	}
	void insert(int &f, int v) {
		split(f, v, x, y);
		f = merge(merge(x, new_node(v)), y);
	}
	void del(int &f, int v) {
		split(f, v, x, z);
		split(x, v - 1, x, y);
		y = merge(son[y][0], son[y][1]);
		f = merge(merge(x, y), z);
	}
	int rank(int &f, int v) {
		split(f, v - 1, x, y);
		int ans = size[x];
		f = merge(x, y);
		return ans;
	}
	int kth(int k, int v) {
		if (!k) return 0;
		if (size[son[k][0]] >= v) return kth(son[k][0], v);
		if (size[son[k][0]] + 1 < v) return kth(son[k][1], v - size[son[k][0]] - 1);
		return val[k];
	}
	int pre(int &f, int v) {
		x = y = 0;
		split(f, v - 1, x, y);
		int ans = x == 0 ? -2147483647 : kth(x, size[x]);
		f = merge(x, y);
		return ans;
	}
	int nxt(int &f, int v) {
		x = y = 0;
		split(f, v, x, y);
		int ans = y == 0 ? 2147483647 : kth(y, 1);
		f = merge(x, y);
		return ans;
	}
} t;
int a[100005];
int f[400005];
void build(int k, int l, int r) {
	for (int i = l; i <= r; i++) t.insert(f[k], a[i]);
	if (l == r) return;
	build(ls, l, mid); build(rs, mid + 1, r);
}
void change(int k, int l, int r, int pos, int x) {
	if (pos < l || pos > r || l == r) return;
//	cout << k << ' ' << l << ' ' << r << endl;
	t.del(f[k], a[pos]); t.insert(f[k], x);
	change(ls, l, mid, pos, x); change(rs, mid + 1, r, pos, x);
}
int rank(int k, int l, int r, int qx, int qy, int val) {
	if (qx <= l && qy >= r) return t.rank(f[k], val);
	int ans = 0;
	if (qx <= mid) ans += rank(ls, l, mid, qx, qy, val);
	if (qy > mid) ans += rank(rs, mid + 1, r, qx, qy, val);
	return ans; 
}
int pre(int k, int l, int r, int qx, int qy, int val) {
	if (qx > r || qy < l) return -2147483647;
	if (qx <= l && qy >= r) return t.pre(f[k], val);
	return max(pre(ls, l, mid, qx, qy, val), pre(rs, mid + 1, r, qx, qy, val));
}
int nxt(int k, int l, int r, int qx, int qy, int val) {
	if (qx > r || qy < l) return 2147483647;
	if (qx <= l && qy >= r) return t.nxt(f[k], val);
	return min(nxt(ls, l, mid, qx, qy, val), nxt(rs, mid + 1, r, qx, qy, val));
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	    cin >> a[i];
	build(1, 1, n);
	for (int i = 1; i <= m; i++) {
		int p, x, y, w; cin >> p;
		if (p == 1) {
			cin >> x >> y >> w;
			cout << rank(1, 1, n, x, y, w) + 1 << endl;
		} else if (p == 2) {
			cin >> x >> y >> w;
			int l = -1, r = 1e8 + 5;
			while (l + 1 < r) {
				int k = l + r >> 1;
				if (rank(1, 1, n, x, y, k) < w) l = mid;
				else r = mid;
			}
			cout << l << endl;
		} else if (p == 3) {
			cin >> x >> w;
			change(1, 1, n, x, w);
			a[x] = w;
		} else if (p== 4) {
			cin >> x >> y >> w;
			cout << pre(1, 1, n, x, y, w) << endl;
		} else {
			cin >> x >> y >> w;
			cout << nxt(1, 1, n, x, y, w) << endl;
		}
	}
	return 0;
}