我写的是线段树套 FHQ-treap，并用 vector 动态分配空间。

#include<bits/stdc++.h>

using namespace std;

struct no_rotate_treap
{
	int root=0;
	int tmp_root1,tmp_root2;
	vector<int> size;
	vector<int> num;
	vector<int> pri;
	vector<int> lson;
	vector<int> rson;
	int cnt=0;
	inline void init()
	{
		cnt=root=0;
		size.clear();size.emplace_back(0);
		num.clear();num.emplace_back(0);
		pri.clear();pri.emplace_back(0);
		lson.clear();lson.emplace_back(0);
		rson.clear();rson.emplace_back(0);
	}
	inline void update(int now)
	{
		size[now]=size[lson[now]]+size[rson[now]]+1;
	}
	inline int add(int val)
	{
		cnt++;
		pri.emplace_back(rand());
		size.emplace_back(1);
		num.emplace_back(val);
		lson.emplace_back(0);
		rson.emplace_back(0);
		return cnt;
	}
	void split(int now,int the_val,int &l,int &r)
	{
		if(!now)
		{
			l=r=0;
			return;
		}
		if(num[now]<=the_val)
		{
			l=now;
			split(rson[now],the_val,rson[now],r);
		}
		else
		{
			r=now;
			split(lson[now],the_val,l,lson[now]);
		}
		update(now);
	}
	int merge(int l,int r)
	{
		if(l&&r)
		{
			if(pri[l]<pri[r])
			{
				lson[r]=merge(l,lson[r]);
				update(r);
				return r;
			}
			else
			{
				rson[l]=merge(rson[l],r);
				update(l);
				return l;
			}
		}
		else return l+r;
	}
	__inline void insert(int x)
	{
		static int t;t=add(x);
		split(root,x,tmp_root1,tmp_root2);
		t=merge(tmp_root1,t);
		root=merge(t,tmp_root2);
	}
	__inline void erase(int x)
	{
		split(root,x,tmp_root1,tmp_root2);
		static int t;
		split(tmp_root1,x-1,tmp_root1,t);
		tmp_root1=merge(tmp_root1,lson[t]);
		tmp_root2=merge(rson[t],tmp_root2);
		root=merge(tmp_root1,tmp_root2);
	}
	__inline int rank(int x)
	{
		split(root,x-1,tmp_root1,tmp_root2);
		static int ans;ans=size[tmp_root1];
		root=merge(tmp_root1,tmp_root2);
		return ans;
	}
	int kth(int now,int k)
	{
		if(now==0)return -2147483647;
		if(size[lson[now]]>=k)return kth(lson[now],k);
		else if(size[lson[now]]+1==k)return num[now];
		else return kth(rson[now],k-size[lson[now]]-1);
	}
	__inline int find_last(int x)
	{
		split(root,x-1,tmp_root1,tmp_root2);
		static int ans;ans=kth(tmp_root1,size[tmp_root1]);
		root=merge(tmp_root1,tmp_root2);
		return ans;
	}
	__inline int find_next(int x)
	{
		split(root,x,tmp_root1,tmp_root2);
		static int ans;ans=kth(tmp_root2,1);
		if(ans==-2147483647)ans=2147483647;
		root=merge(tmp_root1,tmp_root2);
		return ans;
	}
	void print(int now)
	{
		if(!now)return;
		print(lson[now]);
		printf("num=%d,val=%d,pri=%d,size=%d,lson=%d,rson=%d\n",now,num[now],pri[now],size[now],lson[now],rson[now]);
		print(rson[now]);
	}
};//FHQ-treap

const int segment_maxn=(5e4+10)*4;

struct Segment_tree
{
	int n[segment_maxn];
	no_rotate_treap tree[segment_maxn];
	inline int lson(int n){return n<<1;}
	inline int rson(int n){return (n<<1)|1;}
	void btree(int a,int l,int r)
	{
		tree[a].init();
		for(int i=l;i<=r;i++)tree[a].insert(n[i]);
    	if(l==r)return;
    	int mid=(l+r)>>1;
    	btree(lson(a),l,mid);
    	btree(rson(a),mid+1,r);
	}
	inline void change(int a,int l,int r,int num,int x)
	{
		tree[a].erase(n[num]);tree[a].insert(x);
    	if(l==r)return;
    	int mid=(l+r)>>1;
    	if(num<=mid)change(lson(a),l,mid,num,x);
    	else change(rson(a),mid+1,r,num,x);
	}
	int ask_rank(int a,int l,int r,int lft,int rgt,int num)
	{
		if(lft<=l&&r<=rgt)return tree[a].rank(num);
		int mid=(l+r)>>1;
		int k=0;
		if(lft<=mid)k+=ask_rank(lson(a),l,mid,lft,rgt,num);
		if(mid<rgt)k+=ask_rank(rson(a),mid+1,r,lft,rgt,num);
		return k;
	}
	int ask_last(int a,int l,int r,int lft,int rgt,int num)
	{
		if(lft<=l&&r<=rgt)return tree[a].find_last(num);
		int mid=(l+r)>>1;
		int k=-2147483647;
		if(lft<=mid)k=max(k,ask_last(lson(a),l,mid,lft,rgt,num));
		if(mid<rgt)k=max(k,ask_last(rson(a),mid+1,r,lft,rgt,num));
		return k;
	}
	int ask_next(int a,int l,int r,int lft,int rgt,int num)
	{
		if(lft<=l&&r<=rgt)return tree[a].find_next(num);
		int mid=(l+r)>>1;
		int k=2147483647;
		if(lft<=mid)k=min(k,ask_next(lson(a),l,mid,lft,rgt,num));
		if(rgt>mid)k=min(k,ask_next(rson(a),mid+1,r,lft,rgt,num));
		return k;
	}
	__inline void btree(int r)
	{
		btree(1,1,r);
	}
	__inline void changeit(int maxa,int x,int add)
	{
		change(1,1,maxa,x,add);
		n[x]=add;
	}
	__inline int ask_rank(int maxa,int l,int r,int k)
	{
		return ask_rank(1,1,maxa,l,r,k)+1;
	}
	__inline int ask_last(int maxa,int l,int r,int k)
	{
		return ask_last(1,1,maxa,l,r,k);
	}
	__inline int ask_next(int maxa,int l,int r,int k)
	{
		return ask_next(1,1,maxa,l,r,k);
	}
	__inline int ask_kth(int maxa,int l,int r,int k)
	{
		static int ll,rr,mid;ll=tree[1].kth(tree[1].root,k)-1,rr=tree[1].kth(tree[1].root,maxa)+1;
		while(ll<rr-1)
		{
			mid=(ll+rr)>>1;
			//printf("mid=%d,num=%d,k=%d\n",mid,ask_rank(maxa,l,r,mid),k);
			if(ask_rank(maxa,l,r,mid)<=k)ll=mid;
			else rr=mid;
		}
		return ll;
	}
};//segment_tree
Segment_tree tree;

int main()
{
	//freopen("P3380_9.in","r",stdin);
	//freopen("P3380_9.out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>tree.n[i];
	tree.btree(n);
	for(int i=1;i<=m;i++)
	{
		int t1,t2,t3,t4;cin>>t1>>t2;
		switch(t1)
		{
			case 1:cin>>t3>>t4;cout<<tree.ask_rank(n,t2,t3,t4)<<'\n';break;
			case 2:cin>>t3>>t4;cout<<tree.ask_kth(n,t2,t3,t4)<<'\n';break;
			case 3:cin>>t3;tree.changeit(n,t2,t3);break;
			case 4:cin>>t3>>t4;cout<<tree.ask_last(n,t2,t3,t4)<<'\n';break;
			case 5:cin>>t3>>t4;cout<<tree.ask_next(n,t2,t3,t4)<<'\n';break;
		}
	}
}