动态开点线段树

多用于 权值线段树

用多少点开多少点，空间复杂度降至 $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
#define INF 10000000
struct node_val_tree
{
	int l,r,mid;
	int ls,rs;
	int d;
};
struct val_tree
{
	int tot;
	node_val_tree t[N*4];
	void build(int l,int r)
	{
		t[1].l=l;t[1].r=r;t[1].d=0;
		t[1].ls=t[1].rs=0;t[1].mid=(l+r)>>1;
		tot=1;return;
	}
	void insert(int &i,int l,int r,int k,int val)
	{
		if(!i)
		{
			i=++tot;
			t[i].l=l;t[i].r=r;t[i].mid=(l+r)>>1;
			t[i].d=t[i].ls=t[i].rs=0;
		}
		if(l==r)
		{
			if(t[i].d+val>=0) t[i].d+=val;
			return;
		}
		if(k<=t[i].mid) insert(t[i].ls,l,t[i].mid,k,val);
		if(t[i].mid+1<=k) insert(t[i].rs,t[i].mid+1,r,k,val);
		t[i].d=(t[t[i].ls].d+t[t[i].rs].d);
		return;
	}
	int query(int i,int l,int r)
	{
		if(!i) 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(t[i].ls,l,r);
		if(t[i].mid+1<=r) res+=query(t[i].rs,l,r);
		return res;
	}
	int rk(int k)
	{ 
		if(k<=-INF) return 1;
		return query(1,-INF,k-1)+1;
	}
	int kth(int i,int k)
	{
		if(!i) return 0;
		if(t[i].l==t[i].r)
		{
			return t[i].l;
		}
		int res=0;
		if(k<=t[t[i].ls].d) res+=kth(t[i].ls,k);
		if(t[t[i].ls].d+1<=k) res+=kth(t[i].rs,k-t[t[i].ls].d);
		return res; 
	}
	int pre(int k)
	{
		return kth(1,rk(k)-1);
	}
	int nxt(int k)
	{
		return kth(1,rk(k+1));
	}
}t;
int n;
int main()
{
	scanf("%d",&n);
	t.build(-INF,INF);
	for(int i=1;i<=n;++i)
	{
		int opt,x;
		scanf("%d%d",&opt,&x);
		if(opt==1)
		{
			int s=1;
			t.insert(s,-INF,INF,x,1);
		}
		if(opt==2)
		{
			int s=1;
			t.insert(s,-INF,INF,x,-1);
		}
		if(opt==3)
		{
			printf("%d\n",t.rk(x));
		} 
		if(opt==4)
		{
			printf("%d\n",t.kth(1,x));
		}
		if(opt==5)
		{
			printf("%d\n",t.pre(x));
		}
		if(opt==6)
		{
			printf("%d\n",t.nxt(x));
		}
	}
	return 0;
}