题目：二逼平衡树 及其启示

改变数据结构的写法了， 以后就把所有抽象数据类型塞到namespace
里去了qwq

// WA、 TEL 且 RE 的代码， 以后再调
#include<bits/stdc++.h>
using namespace std;
const int maxlog = 20;

namespace fhq {
	
	const int maxn = maxlog * 50000 + 1001;
	int siz[maxn] ,ls[maxn], rs[maxn], rnd[maxn], val[maxn], tot;
	
	int newnode(int v)
	{
		val[++tot] = v; rnd[tot] = rand(); siz[tot] = 1;
//		ls[tot] = rs[tot] = 0;
		return tot;
	}
	
	void update(int k)
	{
		siz[k] = siz[ls[k]] + siz[rs[k]] + 1;
	}
	
	void merge(int &k,int a, int b)
	{
		if(!a || !b)
		{
			k = a + b;
			return;
		}
		if(rnd[a] < rnd[b])
		{
			k = a;
			merge(rs[a], rs[a], b);
		}
		else
		{
			k = b;
			merge(ls[b], a, ls[b]);
		}
		update(k);
	}
	
	void split(int k, int &a, int &b, int weight)
	{
		if(!k)
		{
			a = b = 0;
			return;
		}
		if(val[k] <= weight)
		{
			a = k;
			split(rs[a], rs[a], b, weight);
		}
		else
		{
			b = k;
			split(ls[b], a, ls[b], weight);
		}
		update(k);
	}
	
	void ins(int &rt, int v)
	{
		int a = 0, b = 0;
		split(rt, a, b, v);
		merge(a, a, newnode(v));
		merge(rt, a, b);
	}
	
	int quesrank(int &rt, int k)
	{
		int a = 0, b = 0;
		split(rt, a, b, k-1);
		int ret = siz[a];
		merge(rt, a, b);
		return ret;
	}
	
	void del(int &rt,int k)
	{
		int a = 0, b = 0, c = 0;
		split(rt, a, c, k);
		split(a, a, b, k-1);
		merge(b, ls[b], rs[b]);
		merge(a, a, b);
		merge(rt, a, c);
	}
	
	int ma(int p)
	{
		if(!siz[p]) return -2147483647;
		while(rs[p]) p=rs[p];
		return val[p];
	}
	
	int mi(int p)
	{
		if(!siz[p]) return 2147483647;
		while(ls[p]) p=ls[p];
		return val[p];
	}
	
	int pre(int &rt,int k)
	{
		int a = 0, b = 0;
		split(rt, a, b, k-1);
		int ret = ma(a);
		merge(rt, a, b);
		return ret;
	}
	
	int nxt(int &rt,int k)
	{
		int a = 0, b = 0;
		split(rt, a, b, k);
		int ret = mi(b);
		merge(rt, a, b);
		return ret;
	}
	
}

namespace seg {
	
	const int maxn = maxlog * 50000;
	
	int ls[maxn], rs[maxn], fhqrt[maxn];
	int rt, tot, n;
	
	int m, vec[5005];
	
	void build(int* a, int &u, int l,int r)
	{
		if(!u) u = ++tot;
		//
		for(int i=l; i<=r; ++i) fhq::ins(fhqrt[u], a[i]);
		//build fhq
		if(l == r) return;
		int mid = (l + r) >> 1;
		build(a, ls[u], l, mid);
		build(a, rs[u], mid + 1, r);
	}
	
	void vis(int u, int l,int r,int x,int y)
	{
		if(x<=l && r<=y) {
			vec[++m] = u;
			return;
		}
		int mid = (l + r) >> 1;
		if(x <= mid) vis(ls[u], l, mid, x, y);
		if(y > mid) vis(rs[u], mid + 1, r, x, y);
	}
	
	void getvec(int l,int r)
	{
		m = 0;
		vis(rt, 1, n, l, r);
	}
	
	int quesrank(int l,int r,int k)
	{
		getvec(l, r);
		int ret = 0;
		for(int i=1; i<=m; ++i)
		{
			ret += fhq::quesrank(fhqrt[vec[i]], k);
		}
		return ret + 1;
	}
	
	int queskth(int l,int r,int k)
	{
		int L = 0, R = 100000000;
		while(L!=R)
		{
			int mid = (L+R+1) >> 1;
			if(quesrank(l, r, mid) > k) R = mid-1;
			else L = mid;
		}
		return L;
	}
	
	//modify(seg::rt, 1, n, pos, k);
	int modify(int u, int l,int r,int pos,int k)
	{
		
		if(l == r) {
			int ret = fhq::val[fhqrt[u]];
			fhq::del(fhqrt[u], ret);
			fhq::ins(fhqrt[u], k);
			return ret;
		}
		int mid = (l+r) >> 1; int d;
		if(pos<=mid) d = modify(ls[u], l, mid, pos, k);
		else d = modify(rs[u], mid + 1, r, pos, k);
		fhq::del(fhqrt[u], d);
		fhq::ins(fhqrt[u], k);
		
		return 1;
		
	}
	
	int quesprev(int l,int r,int k)
	{
		getvec(l, r);
		int ret = -2147483647;
		for(int i=1; i<=m; ++i)
		{
			ret = max(ret, fhq::pre(fhqrt[vec[i]], k));
		}
		return ret;
	}
	
	int quesnext(int l,int r,int k)
	{
		getvec(l, r);
		int ret = 2147483647;
		for(int i=1; i<=m; ++i)
		{
			ret = min(ret, fhq::nxt(fhqrt[vec[i]], k));
		}
		return ret;
	} 
	
}

int a[50005], n, m;

int main()
{
	
	srand((unsigned)time(0));
	
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
	seg::build(a, seg::rt, 1, n);
	seg::n = n;
	
	while(m--)
	{
		int opt; scanf("%d", &opt);
		if(opt == 1)
		{
			int l, r, k; scanf("%d%d%d", &l, &r, &k);
			cout << seg::quesrank(l, r, k) << '
';
		}
		if(opt == 2)
		{
			int l, r, k; scanf("%d%d%d", &l, &r, &k);
			cout << seg::queskth(l, r, k) << '
';
		}
		if(opt == 3)
		{
			int pos, k; scanf("%d%d", &pos, &k);
			seg::modify(seg::rt, 1, n, pos, k);
		}
		if(opt == 4)
		{
			int l, r, k; scanf("%d%d%d", &l, &r, &k);
			cout << seg::quesprev(l, r, k) <<'
';
		}
		if(opt == 5)
		{
			int l, r, k; scanf("%d%d%d", &l, &r, &k);
			cout << seg::quesnext(l, r, k) <<'
';
		}
	}
	
	return 0;
	
}