50pts球跳

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>

#define int long long
#define function auto
#define rop(a, b, c) for(int a = b; a < c; ++ a)
#define por(a, b, c) for(int a = b; a > c; -- a)
#define rep(a, b, c) for(int a = b; a <= c; ++ a)
#define per(a, b, c) for(int a = b; a >= c; -- a)
#define resetIO(str) freopen(#str".in", "r", stdin),\
					 freopen(#str".out", "w", stdout)

typedef long long LL;

constexpr int N = 1e5 + 10;
constexpr int inf = 2147483647;

namespace Space {
	
	function lowbit = [](int x) -> int {
		return x & (-x);
	};

	template < typename _Tp > inline function
	read(_Tp& t) -> void {
		int f = 0, ch = getchar (); t = 0;
		while (!isdigit(ch)) f |= ch == '-', ch = getchar ();
		do {t = (t << 1) + (t << 3) +(ch ^ '0'); ch = getchar ();}
		while (isdigit(ch)); t = f ? -t : t;
	}
	
	template < typename _Tp, typename... _Args > inline function
	read(_Tp& t, _Args&... args) -> void {
		read(t); read(args...);
	}
} using namespace Space;

struct seg{
	int v, ls, rs;
}t[N << 7];

struct az{
	int a, b, c, d;
}q[N << 1];

int len = 0;
int rt[N << 1], n, m, tot, tem[N << 1], tmp[N << 1], cnt, num;
int lsh[N << 1], a[N << 1];

class SegmentTree {
private:
	inline function
	pushup(int o) -> void {
		t[o].v = t[t[o].ls].v + t[t[o].rs].v;
	}

	inline function
	add(int o, int v) -> void {
		for (int i = o; i <= n; i += lowbit(i))
			this -> change(rt[i], 1, len, a[o], v);
	}

	inline function
	change(int& o, int l, int r, int k, int v) -> void {
		if (!o) o = ++ tot;
		if (l == r) {
			t[o].v += v; return;
		} int mid = (l + r) >> 1;
		if (k <= mid) this -> change(t[o].ls, l, mid, k, v);
		else this -> change(t[o].rs, mid + 1, r, k, v);
		this -> pushup(o);
	}

	inline function
	query_num(int l, int r, int k) -> int {
		if (l == r) return l;
		int mid = (l + r) >> 1, sum = 0;
		rep(i, 1, cnt) sum += t[t[tem[i]].ls].v;
		rep(i, 1, num) sum -= t[t[tmp[i]].ls].v;
		if (k <= sum) {
			rep(i, 1, cnt) tem[i] = t[tem[i]].ls;
			rep(i, 1, sum) tmp[i] = t[tmp[i]].ls;
			return this -> query_num(l, mid, k);
		} else {
			rep(i, 1, cnt) tem[i] = t[tem[i]].rs;
			rep(i, 1, sum) tmp[i] = t[tmp[i]].rs;
			return this -> query_num(mid + 1, r, k - sum);
		}
	}

	inline function
	find_num(int l, int r, int k) -> int {
		cnt = num = 0;
		for (int i = r; i; i -= lowbit(i)) tem[++ cnt] = rt[i];
		for (int i = l - 1; i; i -= lowbit(i)) tmp[++ num] = rt[i];
		return this -> query_num(1, len, k);
	}

	inline function
	query_rnk(int l, int r, int k) -> int {
		if (l == r) return 0;
		int mid = (l + r) >> 1, sum = 0;
		if (k <= mid) {
			rep(i, 1, cnt) tem[i] = t[tem[i]].ls;
			rep(i, 1, num) tmp[i] = t[tmp[i]].ls;
			return this -> query_rnk(l, mid, k);
		} else {
			rep(i, 1, cnt) sum += t[t[tem[i]].ls].v, tem[i] = t[tem[i]].rs;
			rep(i, 1, num) sum -= t[t[tmp[i]].ls].v, tmp[i] = t[tmp[i]].rs;
			return sum + this -> query_rnk(mid + 1, r, k);
		}
	}

	inline function
	find_rnk(int l, int r, int k) -> int {
		cnt = num = 0;
		for (int i = r; i ; i -= lowbit(i)) tem[++ cnt] = rt[i];
		for (int i = l - 1; i; i -= lowbit(i)) tmp[++ num] = rt[i];
		return this -> query_rnk(1, len, k) + 1;
	}

	inline function
	find_pri(int l, int r, int k) -> int {
		int rk = this -> find_rnk(l, r, k) - 1;
		if (!rk) return 0;
		return this -> find_num(l, r, rk);
	}

	inline function
	find_nxt(int l, int r, int k) -> int {
		if (k == len) return{len + 1};
		int rk = this -> find_rnk(l, r, k + 1);
		if (rk == r - l + 2) return{len + 1};
		return this -> find_num(l, r, rk);
	}

public:
	inline function
	solve() -> void {
		read(n, m); tot = cnt = num = 0;
		rep(i, 1, n) read(a[i]), lsh[++ len] = a[i];
		rep(i, 1, m) {
			read(q[i].a, q[i].b, q[i].c);
			if (q[i].a != 3) read(q[i].d);
			else lsh[++ len] = q[i].c;
			if (q[i].a == 4 || q[i].a == 5) lsh[++ len] = q[i].d;
		} std::sort(lsh + 1, lsh + len + 1);
		len = std::unique(lsh + 1, lsh + len + 1) - lsh - 1;
		rep(i, 1, n) {
			a[i] = std::lower_bound(lsh + 1, lsh + 1 + len, a[i]) - lsh;
			this -> add(i, 1);
		} lsh[0] = -inf; lsh[len + 1] = inf; rep(i, 1, m) {
			if (q[i].a == 3) {
				this -> add(q[i].b, -1);
				a[q[i].b] = std::lower_bound(lsh + 1, lsh + 1 + len, q[i].c) - lsh;
				this -> add(q[i].b, 1);
			}
			if (q[i].a == 1) {
				q[i].d = std::lower_bound(lsh + 1, lsh + 1 + len, q[i].d) - lsh;
				std::printf("%lld\n", this -> find_rnk(q[i].b, q[i].c, q[i].d));
			} 

			if (q[i].a == 2) {
				std::printf("%lld\n", lsh[this -> find_num(q[i].b, q[i].c, q[i].d)]);
			}

			if (q[i].a == 4) {
				q[i].d = std::lower_bound(lsh + 1, lsh + 1 + len, q[i].d) - lsh;
				std::printf("%lld\n", lsh[this -> find_pri(q[i].b, q[i].c, q[i].d)]);
			}

			if (q[i].a == 5) {
				q[i].d = std::lower_bound(lsh + 1, lsh + 1 + len, q[i].d) - lsh;
				std::printf("%lld\n", lsh[this -> find_nxt(q[i].b, q[i].c, q[i].d)]);
			}
		}
	}
}tree;

signed main() {
	resetIO(data);
	tree.solve();
}