权值线段树

顾名思义，维护权值的线段树。在一定情况下可以代替平衡树使用。

原理是用线段树维护桶，节点维护子树中数的个数。所以空间开销与数据的值域相关。

那要是值域过大怎么办:离散化和动态开点，离散化可以将数据值域缩小到数据数量,将空间复杂度变为 $O(n)$，缺点是需要离线。而需要在线则需支持动态开点，即用多少开多少。

动态开点线段树

权值线段树:支持平衡树操作（翻转除外），并附带离散化

P3369普通平衡树

#include<bits/stdc++.h>
using namespace std;
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define LL long long
#define N 100010
struct node_val_tree
{
	int l,r,mid;
	int d;
};
struct val_tree
{
	node_val_tree t[4*N];
	void build(int i,int l,int r)
	{
		t[i].l=l;t[i].r=r;t[i].mid=(l+r)>>1;
		t[i].d=0;
		if(l==r) return;
		build(i<<1,l,t[i].mid);
		build(i<<1|1,t[i].mid+1,r);
		return;
	}
	void insert(int i,int l,int k)
	{
		if(l==t[i].l&&t[i].r==l)
		{
			if(t[i].d+k>=0)t[i].d+=k;
			return;
		}
		if(l<=t[i].mid) insert(i<<1,l,k);
		if(t[i].mid+1<=l) insert(i<<1|1,l,k);
		t[i].d=(t[i<<1].d+t[i<<1|1].d);
		return; 
	}
	int kth(int i,int k)
	{
		if(t[i].l==t[i].r)
		{
			return t[i].l;
		}
		int res=0;
		if(k<=t[i<<1].d) res+=kth(i<<1,k);
		if(t[i<<1].d+1<=k) res+=kth(i<<1|1,k-t[i<<1].d);
		return res;
	}
	int query(int i,int l,int r)
	{
		if(l>r) return 0;
		if(l<=t[i].l&&t[i].r<=r)
		{
			return t[i].d;
		}
		int res=0;
		if(l<=t[i].mid) res+=query(i<<1,l,r);
		if(t[i].mid+1<=r) res+=query(i<<1|1,l,r);
		return res;
	}
	int rk(int k)
	{
		return query(1,1,k-1)+1;
	}
	int pre(int k)
	{
		return kth(1,rk(k)-1);
	}
	int nxt(int k)
	{
		return kth(1,rk(k+1));
	}
}t;
int n,opt[N],x[N];
int b[N],id[N],tot;
int c[N];
bool cmp_val(int xxx,int yyy)
{
	return b[xxx]<b[yyy]; 
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&opt[i],&x[i]);
		if(opt[i]!=4)
		{
			b[++tot]=x[i];
			id[tot]=tot;
		}
	} 
	sort(id+1,id+1+tot,cmp_val);
	int tmp=b[id[1]],top=1;
	b[id[1]]=top;
	c[top]=tmp;
	for(int i=2;i<=tot;++i)
	{
		if(b[id[i]]!=tmp) ++top;
		tmp=b[id[i]];
		c[top]=b[id[i]];
		b[id[i]]=top;
	}
	top=0;
	t.build(1,1,tot);
	for(int i=1;i<=n;++i)
	{
		if(opt[i]!=4) ++top;
		if(opt[i]==1)
		{
			t.insert(1,b[top],1);
		}
		if(opt[i]==2)
		{
			t.insert(1,b[top],-1);
		}
		if(opt[i]==3)
		{
			printf("%d\n",t.rk(b[top]));
		}
		if(opt[i]==4)
		{
			printf("%d\n",c[t.kth(1,x[i])]);
		}
		if(opt[i]==5)
		{
			printf("%d\n",c[t.pre(b[top])]);
		}
		if(opt[i]==6)
		{
			printf("%d\n",c[t.nxt(b[top])]);
		}
	}
	return 0;
}