RT，只有 20pts
人都呆住了，怎么调都没看出来哪里错了呜呜呜/kk
应该是区间排名那块错了，有巨佬帮忙看看嘛/kel

#include <iostream>
#include <cstdlib>
#include <ctime>
#define MAXN 1000000
using namespace std;
int max(int x, int y) {return ((x > y) ? (x) : (y));}
int min(int x, int y) {return ((x < y) ? (x) : (y));}
//---QWQAQUQ--- 
int n, m, amin = 0x7f7f7f7f, amax = -0x7f7f7f7f;
//---QWQAQUQ---
struct node {
	int val, ls, rs, siz, rnd;
} T[MAXN + 10];
int tot = 0;
int a[50000 + 10];
struct FHQ_traep {
	int root;
	void clear() {tot = root = 0;}
	void updata(int now) {
		T[now].siz = T[T[now].ls].siz + T[T[now].rs].siz + 1; 
	}
	void split(int &x, int &y, int val, int now) {
		if(!now) {x = y = 0; return;}
		else if(T[now].val <= val) x = now, split(T[now].rs, y, val, T[now].rs);
		else y = now, split(x, T[now].ls, val, T[now].ls);
		updata(now);
	}
	int merge(int x, int y) {
		if(!x || !y) return x | y;
		if(T[x].rnd < T[y].rnd) {
			T[x].rs = merge(T[x].rs, y);
			updata(x); return x;
		}
		else {
			T[y].ls = merge(x, T[y].ls);
			updata(y); return y;
		}
	}
	int New(int val) {
		T[++tot].val = val;
		T[tot].rnd = rand();
		T[tot].siz = 1;
		return tot;
	} 
	void Insert(int val) {
		int x, y, z;
		split(x, y, val, root);
		root = merge(merge(x, New(val)), y);
	}
	void Delete(int val) {
		int x, y, z;
		split(x, z, val, root);
		split(x, y, val - 1, x);
		y = merge(T[y].ls, T[y].rs);
		root = merge(merge(x, y), z);
	}
	int Find_rank(int val) {
		int x, y, ans = 0;
		split(x, y, val - 1, root);
		ans = T[x].siz + 1;
		root = merge(x, y);
		return ans;
	}
	int Find_val(int now, int rank) {
		while(233) {
			if(rank <= T[T[now].ls].siz) now = T[now].ls;
			else if(rank == T[T[now].ls].siz + 1) return T[now].val;
			else rank = rank - T[T[now].ls].siz - 1, now = T[now].rs;
		}
	}
	int Pre(int val) {
		int x, y, z, ans = 0;
		split(x, y, val - 1, root);
		if(T[x].siz) ans = Find_val(x, T[x].siz);
		else ans = -2147483647;
		merge(x, y);
		return ans;
	}
	int Next(int val) {
		int x, y, z, ans = 0;
		split(x, y, val, root);
		if(T[y].siz) ans = Find_val(y, 1);
		else ans = 2147483647;
		merge(x, y);
		return ans;
	}
} TT[50000 * 4 + 10];
//QWQAQUQ
int ls(int x) {return (x << 1);}
int rs(int x) {return (x << 1 | 1);}
int F_rank(int l, int r, int s, int t, int now, int val) {
	if(s >= l && t <= r) return TT[now].Find_rank(val) - 1;
	if(s > r || t < l) return 0;
	int mid = (s + t) >> 1;
	return F_rank(l, r, s, mid, ls(now), val) + F_rank(l, r, mid + 1, t, rs(now), val);
}
int F_val(int l, int r, int rank) {
	int L = 0, R = 1e8, ans = 20090725;
	while(L <= R) {
		int mid = (L + R) >> 1;
		if(F_rank(l, r, 1, n, 1, mid) + 1 <= rank) ans = mid, L = mid + 1;
		else R = mid - 1;
	}
	return ans;
}
void T_updata(int l, int r, int pos, int now, int val) {
	TT[now].Delete(a[pos]), TT[now].Insert(val);
	if(l == r) return ;
	int mid = (l + r) >> 1;
	if(pos <= mid) T_updata(l, mid, pos, ls(now), val);
	else T_updata(mid + 1, r, pos, rs(now), val);
}
int T_pre(int l, int r, int s, int t, int now, int val) {
	if(s >= l && t <= r) return TT[now].Pre(val);
	int mid = (s + t) >> 1, res = -2147483647;
	if(l <= mid) res = max(res, T_pre(l, r, s, mid, ls(now), val));
	if(r > mid) res = max(res, T_pre(l, r, mid + 1, t, rs(now), val));
	return res;
}
int T_next(int l, int r, int s, int t, int now, int val) {
	if(s >= l && t <= r) return TT[now].Next(val);
	int mid = (s + t) >> 1, res = 2147483647;
	if(l <= mid) res = min(res, T_next(l, r, s, mid, ls(now), val));
	if(r > mid) res = min(res, T_next(l, r, mid + 1, t, rs(now), val));
	return res;
}
void build(int l, int r, int now) {
	for(int p = l; p <= r; p++) TT[now].Insert(a[p]);
	if(l == r) return ;
	int mid = (l + r) >> 1;
	build(l, mid, ls(now));
	build(mid + 1, r, rs(now)); 
}
//---QWQAQUQ---
int main() {
	srand(time(0));
	cin >> n >> m;
	for(int p = 1; p <= n; p++) {
		cin >> a[p];
		amin = min(amin, a[p]);
		amax = max(amax, a[p]);
	}
	build(1, n, 1);
	int opt, x, y, z;
	while(m--) {
		cin >> opt >> x >> y;
		if(opt == 1) cin >> z, cout << F_rank(x, y, 1, n, 1, z) + 1 << endl;
		else if(opt == 2) cin >> z, cout << F_val(x, y, z) << endl;
		else if(opt == 3) T_updata(1, n, x, 1, y);
		else if(opt == 4) cin >> z, cout << T_pre(x, y, 1, n, 1, z) <<endl;
		else if(opt == 5) cin >> z, cout << T_next(x, y, 1, n, 1, z) << endl; 
	} 
}

码风很丑见谅 qwq