TLE on #2, 2.05s

#include <bits/stdc++.h>

// using fread
#define INPUT_OPTIMIZE

// using fwrite
#define OUTPUT_OPTIMIZE

namespace IO {
	
#ifdef INPUT_OPTIMIZE
	static char buf[1 << 21], *p1 = buf, *p2 = buf;
	#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++
#endif
	
	inline  
	bool read(char *t) {
		memset(t, 0, sizeof t);
		char *p = t, c = getchar();
		while (isspace(c)) c = getchar();
		while (!isspace(c)) *p++ = c, c = getchar();
		return c == EOF;
	}
	
	template 
	<typename T> 
	inline 
	bool read(T &t) {
		t = 0;
    	char c = getchar(); bool f = 1;
    	while (isspace(c)) c = getchar(); 
		if (c == '-') f = 0, c = getchar();
    	while (isdigit(c)) t = (t << 3) + (t << 1) + (c ^ 48), c = getchar();
		t *= f ? 1 : -1;
		return c != EOF;
	}

	template 
	<typename T, typename... Args> 
	inline 
	bool read(T &t, Args&... args) {
		return read(t) && read(args...);
	}

#ifdef OUTPUT_OPTIMIZE
	static char outbuf[1 << 24], *out = outbuf;
	#define putchar(x) *out++ = x
	#define flush() fwrite(outbuf, 1, out - outbuf, stdout)
#else 
   #define flush() 0
#endif

	inline 
	void write(const char* s) {
		int l = strlen(s);
		for (int i = 0; i < l; i++) putchar(s[i]);
	}

	template 
	<typename T> 
	inline 
	void write(T x) {
		if (x < 0) putchar('-'), x = -x;
		if (!x) return putchar('0'), void();
		static char t[20], p = 0;
		while (x) t[++p] = (x % 10) ^ 48, x /= 10;
		while (p) putchar(t[p--]);
	}
	
	template 
	<typename T, typename... Args> 
	inline 
	void write(T t, Args... args) {
		write(t), write(args...);
	}
	
}

using namespace IO;

using namespace std;

typedef long long ll;

const int MAXN = 5e4 + 10;
const int inf = ~0u >> 1;

mt19937 eng(time(0));
uniform_int_distribution<int> dist;

struct node {
	int l, r, val, w, size;
} t[MAXN << 6]; int cnt;

inline 
int create(int val) {
	return t[++cnt] = { 0, 0, val, dist(eng), 1 }, cnt;
}

inline 
void pushup(int p) {
	t[p].size = t[t[p].l].size + t[t[p].r].size + 1;
}

void split(int p, int val, int &x, int &y) {
	if (!p) return x = y = 0, void();
	if (t[p].val <= val) x = p, split(t[x].r, val, t[x].r, y), pushup(x);
	else y = p, split(t[y].l, val, x, t[y].l), pushup(y);
}

int merge(int x, int y) {
	if (!x || !y) return x | y;
	if (t[x].w > t[y].w) return t[x].r = merge(t[x].r, y), pushup(x), x;
	else return t[y].l = merge(x, t[y].l), pushup(y), y;
}

inline 
int kth(int p, int k) {
	while (1) {
		if (t[t[p].l].size >= k) p = t[p].l;
		else if (t[t[p].l].size + 1 == k) return t[p].val;
		else k -= t[t[p].l].size + 1, p = t[p].r;
	}
}

inline 
void insert(int &p, int val) {
	int l, r;
	split(p, val, l, r), p = merge(merge(l, create(val)), r);
}

inline 
void erase(int &p, int val) {
	int l, x, r;
	split(p, val, l, r), split(l, val - 1, l, x), p = merge(merge(l, merge(t[x].l, t[x].r)), r);
}

inline 
int rnk(int &p, int val) {
	int res, l, r;
	split(p, val - 1, l, r), res = t[l].size, p = merge(l, r);
	return res;
}

inline 
int pre(int &p, int val) {
	int res, l, r;
	split(p, val - 1, l, r), res = t[l].size ? kth(l, t[l].size) : -inf, merge(l, r);
	return res;
}

inline 
int nxt(int &p, int val) {
	int res, l, r;
	split(p, val, l, r), res = t[r].size ? kth(r, 1) : inf, merge(l, r);
	return res;
}

int a[MAXN];

struct segtree {
	int l, r, rt;
} s[MAXN << 2];

void build(int l, int r, int p) {
	s[p].l = l, s[p].r = r;
	for (int i = l; i <= r; i++) insert(s[p].rt, a[i]);
	if (l == r) return ;
	int mid = l + r >> 1;
	build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
}

void modify(int k, int val, int p) {
	erase(s[p].rt, a[k]), insert(s[p].rt, val);
	if (s[p].l == s[p].r) return ;
	int mid = s[p].l + s[p].r >> 1;
	modify(k, val, p << 1 | mid < k);
}

int qrnk(int l, int r, int val, int p) {
	if (l <= s[p].l && s[p].r <= r) return rnk(s[p].rt, val);
	int mid = s[p].l + s[p].r >> 1, rnk = 0;
	if (l <= mid) rnk += qrnk(l, r, val, p << 1);
	if (r > mid) rnk += qrnk(l, r, val, p << 1 | 1);
	return rnk;
}

inline 
int qkth(int l, int r, int k) {
	int x = 0, y = 1e8, mid;
	while (x < y) mid = x + y + 1 >> 1, qrnk(l, r, mid, 1) < k ? x = mid : y = mid - 1;
	return y;
}

int qpre(int l, int r, int val, int p) {
	if (l <= s[p].l && s[p].r <= r) return pre(s[p].rt, val);
	int mid = s[p].l + s[p].r >> 1, res = -inf;
	if (l <= mid) res = max(res, qpre(l, r, val, p << 1));
	if (r > mid) res = max(res, qpre(l, r, val, p << 1 | 1));
	return res;
}

int qnxt(int l, int r, int val, int p) {
	if (l <= s[p].l && s[p].r <= r) return nxt(s[p].rt, val);
	int mid = s[p].l + s[p].r >> 1, res = inf;
	if (l <= mid) res = min(res, qnxt(l, r, val, p << 1));
	if (r > mid) res = min(res, qnxt(l, r, val, p << 1 | 1));
	return res;
}

int n, m;

int opt, l, r, k;

int main() {
	read(n, m);
	for (int i = 1; i <= n; i++) read(a[i]);
	build(1, n, 1);
	while (m--) {
    	read(opt, l);
    	switch (opt) {
    	case 1: read(r, k), write(qrnk(l, r, k, 1) + 1, "\n"); break;
    	case 2: read(r, k), write(qkth(l, r, k), "\n"); break;
    	case 3: read(k), modify(l, k, 1), a[l] = k; break;
    	case 4: read(r, k), write(qpre(l, r, k, 1), "\n"); break;
    	case 5: read(r, k), write(qnxt(l, r, k, 1), "\n"); break;
		}
	}
	flush();
}