Description：

写一种数据结构，来维护一个有序数列，其中需要提供以下操作：

1. 查询 $k$ 在区间内的排名 2. 查询区间内排名为 $k$ 的值 3. 修改某一位值上的数值 4. 查询k在区间内的前驱( 前驱定义为严格小于 $x$ ，且最大的数，若不存在输出 $-2147483647$ ) 5. 查询k在区间内的后继( 后继定义为严格大于 $x$ ，且最小的数，若不存在输出 $2147483647$ )

$1\le n \le 5\times 10^4$

Solution：

线段树套平衡树，线段树上每个节点存储着一棵平衡树的根，平衡树内存储着这个区间的数字，每次将涉及到的 $long\ n$ 个区间的平衡树取出来，操作 $1$ 直接把所有平衡树的 $rank$ 加在一起，操作 $4,5$ 对每棵平衡树的值取 $min/max$ ， $3$ 操作在从根到叶子结点的链上插入新数，删除原数， $2$ 操作先二分一个值，判断是否有足够多的数比它小，然后调整二分边界即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 50010

#define INF 2147483647

int a[MAXN];

namespace treap

{

	struct node

	{

		int lc,rc;

		int siz,val,cnt,ran;

		node(){lc = rc = siz = val = cnt = ran = 0;}

		void clear(){lc = rc = siz = val = cnt = ran = 0;}

	}t[MAXN * 31];

	int ptr = 0;

	int del_node[MAXN * 31],del_ptr = 0;

	inline int newnode()

	{

		if(del_ptr != 0){int k = del_node[del_ptr--];t[k].clear();return k;}

		else return ++ptr;

	}

	inline void maintain(int rt)

	{

		t[rt].siz = t[t[rt].lc].siz + t[t[rt].rc].siz + t[rt].cnt;

		return;

	}

	inline void lturn(int &k)

	{

		register int p = t[k].rc;t[k].rc = t[p].lc;t[p].lc = k;

		t[p].siz = t[k].siz;maintain(k);k = p;

		return;

	}

	inline void rturn(int &k)

	{

		register int p = t[k].lc;t[k].lc = t[p].rc;t[p].rc = k;

		t[p].siz = t[k].siz;maintain(k);k = p;

		return;

	}

	void insert(int &k,int x)

	{

		if(k == 0)

		{

			k = newnode();

			t[k].siz = 1;t[k].cnt = 1;t[k].val = x;t[k].ran = rand();

			return;

		}

		++t[k].siz;

		if(t[k].val == x){++t[k].cnt;return;}

		if(x < t[k].val)

		{

			insert(t[k].lc,x);

			if(t[t[k].lc].ran < t[k].ran)rturn(k);

		}

		else

		{

			insert(t[k].rc,x);

			if(t[t[k].rc].ran < t[k].ran)lturn(k);

		}

		return;

	}

	void remove(int &k,int x)

	{

		if(t[k].val == x)

		{

			if(t[k].cnt > 1){--t[k].cnt;--t[k].siz;return;}

			if(t[k].lc == 0 || t[k].rc == 0)

			{

				del_node[++del_ptr] = k;

				if(t[k].lc == 0)k = t[k].rc;

				else k = t[k].lc;

				return;

			}

			if(t[t[k].lc].ran < t[t[k].rc].ran){rturn(k);remove(k,x);}

			else{lturn(k);remove(k,x);}

			return;

		}

		else

		{

			if(x < t[k].val){--t[k].siz;remove(t[k].lc,x);}

			else{--t[k].siz;remove(t[k].rc,x);}

			return;

		}

	}

	int pre(int k,int x)

	{

		if(k == 0)return -INF;

		if(x <= t[k].val)return pre(t[k].lc,x);

		int p = pre(t[k].rc,x);

		if(p == -INF)return t[k].val;

		else return p;

	}

	int nxt(int k,int x)

	{

		if(k == 0)return INF;

		if(x >= t[k].val)return nxt(t[k].rc,x);

		int p = nxt(t[k].lc,x);

		if(p == INF)return t[k].val;

		else return p;

	}

	int rank(int k,int x)

	{

		if(k == 0)return 0;

		if(x == t[k].val)return t[t[k].lc].siz;

		if(x < t[k].val)return rank(t[k].lc,x);

		if(x > t[k].val)return rank(t[k].rc,x) + t[t[k].lc].siz + t[k].cnt;

	}

	int num(int k,int x)

	{

		if(x <= t[t[k].lc].siz)return num(t[k].lc,x);

		if(x > t[t[k].lc].siz + t[k].cnt)return num(t[k].rc,x);

		return t[k].val;

	}

}

namespace seg

{

	struct node

	{

		int lc,rc;

		int root;

	}t[MAXN << 1];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root;

	#define mid ((l + r) >> 1)

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		t[rt].root = 0;

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	int roots[32],tot = 0;

	void get(int rt,int L,int R,int l,int r)

	{

		if(L <= l && r <= R)

		{

			roots[++tot] = t[rt].root;

			return;

		}

		if(L <= mid)get(t[rt].lc,L,R,l,mid);

		if(R > mid)get(t[rt].rc,L,R,mid + 1,r);

		return;

	}

	void insert(int rt,int p,int k,int l,int r)

	{

		treap::insert(t[rt].root,k);

		if(l == r)return;

		if(p <= mid)insert(t[rt].lc,p,k,l,mid);

		else insert(t[rt].rc,p,k,mid + 1,r);

		return;

	}

	void remove(int rt,int p,int k,int l,int r)

	{

		treap::remove(t[rt].root,k);

		if(l == r)return;

		if(p <= mid)remove(t[rt].lc,p,k,l,mid);

		else remove(t[rt].rc,p,k,mid + 1,r);

		return;

	}

}

int rank()

{

	int l,r,k;

	scanf("%d%d%d",&l,&r,&k);

	seg::tot = 0;

	seg::get(seg::root,l,r,1,n);

	int ans = 0;

	for(int i = 1;i <= seg::tot;++i)

	{

		ans += treap::rank(seg::roots[i],k);

	}

	return ans + 1;

}

int num()

{

	int L,R,k;

	scanf("%d%d%d",&L,&R,&k);

	seg::tot = 0;

	seg::get(seg::root,L,R,1,n);

	int l = 0,r = 1e8,cen;

	while(l < r)

	{

		cen = ((l + r + 1) >> 1);

		int sum = 0;

		for(int i = 1;i <= seg::tot;++i)

		{

			sum += treap::rank(seg::roots[i],cen);

		}

		sum += 1;

		if(sum > k)r = cen - 1;

		else l = cen;

	}

	return l;

}

void change()

{

	int p,k;

	scanf("%d%d",&p,&k);

	seg::remove(seg::root,p,a[p],1,n);

	a[p] = k;

	seg::insert(seg::root,p,a[p],1,n);

	return;

}

int pre()

{

	int l,r,k;

	scanf("%d%d%d",&l,&r,&k);

	seg::tot = 0;

	seg::get(seg::root,l,r,1,n);

	int ans = -INF;

	for(int i = 1;i <= seg::tot;++i)

	{

		ans = max(ans,treap::pre(seg::roots[i],k));

	}

	return ans;

}

int nxt()

{

	int l,r,k;

	scanf("%d%d%d",&l,&r,&k);

	seg::tot = 0;

	seg::get(seg::root,l,r,1,n);

	int ans = INF;

	for(int i = 1;i <= seg::tot;++i)

	{

		ans = min(ans,treap::nxt(seg::roots[i],k));

	}

	return ans;

}

int main()

{ 

	srand(time(NULL));

	scanf("%d%d",&n,&m);

	seg::build(seg::root,1,n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a[i]);

		seg::insert(seg::root,i,a[i],1,n);

	}

	int type;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&type);

		switch (type)

		{

			case 1:{printf("%d\n",rank());break;}

			case 2:{printf("%d\n",num());break;}

			case 3:{change();break;}

			case 4:{printf("%d\n",pre());break;}

			case 5:{printf("%d\n",nxt());break;}

		}

	}

	return 0;

}