BST(支持重复元素)

#include<bits/stdc++.h>
using namespace std;
template<int Size>
class BST
{
	protected:
		struct node
		{
			int data,size,t,ls,rs;
		};
		node v[Size];
		int root=1,tot=0,INF=1<<30;
		void up(int index)
		{
			v[index].size=v[index].t+v[v[index].ls].size+v[v[index].rs].size;
		}
		int new_p(int x)
		{
			v[++tot]={x,1,1,0,0};
			return tot;
		}
		int find(int x,int index)
		{
			if(!index)return 0;
			if(x==v[index].data)return index;
			if(x<v[index].data)return find(x,v[index].ls);
			return find(x,v[index].rs);
		}
		void push(int x,int &index)
		{
			if(!index)
			{
				index=new_p(x);
				return;
			}
			if(x==v[index].data)
			{
				v[index].t++,up(index);
				return;
			}
			if(x<v[index].data)push(x,v[index].ls);
			else push(x,v[index].rs);
			up(index);
		}
		void pop(int x,int &index)
		{
			if(!index)return;
			if(x==v[index].data)
			{
				if(v[index].t>1)v[index].t--,up(index);
				else if(!v[index].ls || !v[index].rs)
					index=v[index].ls+v[index].rs;
				else
				{
					int p=v[index].rs;
					while(v[p].ls)p=v[p].ls;
					pop(v[p].data,v[index].rs);
					v[p].ls=v[index].ls,v[p].rs=v[index].rs;
					index=p;
				}
				return;
			}
			if(x<v[index].data)pop(x,v[index].ls);
			else pop(x,v[index].rs);
			up(index);
		}
		int next_p(int x)
		{
			int index=root;
			int ans=2;//INF
			while(index)
			{
				if(x==v[index].data)
				{
					if(!v[index].rs)break;
					index=v[index].rs;
					while(v[index].ls)index=v[index].ls;
					ans=index;break;
				}
				if(v[index].data>x && v[index].data<v[ans].data)ans=index;
				if(x<v[index].data)index=v[index].ls;
				else index=v[index].rs;
			}
			return ans;
		}
		int prev_p(int x)
		{
			int index=root;
			int ans=1;
			while(index)
			{
				if(x==v[index].data)
				{
					if(!v[index].ls)break;
					index=v[index].ls;
					while(v[index].rs)index=v[index].rs;
					ans=index;break;
				}
				if(v[index].data<x && v[index].data>v[ans].data)ans=index;
				if(x<v[index].data)index=v[index].ls;
				else index=v[index].rs;
			}
			return ans;
		}
	public:
		BST()
		{
			new_p(-INF),new_p(INF);
			root=1,v[1].rs=2;
			up(1);
		}
		int size()
		{
			return v[root].size-2;
		}
		int find(int x)
		{
			return find(x,root);
		}
		int get_next(int x)
		{
			return v[next_p(x)].data;
		}
		int get_prev(int x)
		{
			return v[prev_p(x)].data;
		}
		void push(int x)
		{
			push(x,root);
		}
		void pop(int x)
		{
			pop(x,root);
		}
};
class ni_BST:public BST<100005>
{
	public:
		void out(int index=1)
		{
			if(!index)return;
			out(v[index].ls);
			if(abs(v[index].data)!=INF)
				for(int i=1;i<=v[index].t;i++)cout<<v[index].data<<" ";
			out(v[index].rs);
		}
}a;
int main()
{
	while(1)
	{
		char o;cin>>o;
		if(o=='>')
		{
			int x;cin>>x;
			a.push(x);
		}
		if(o=='<')
		{
			int x;cin>>x;
			a.pop(x);
		}
		if(o=='n')
		{
			int x;cin>>x;
			cout<<x<<" next: "<<a.get_next(x)<<"\n";
		}
		if(o=='p')
		{
			int x;cin>>x;
			cout<<x<<" prev: "<<a.get_prev(x)<<"\n";
		}
		if(o=='s')
			cout<<"size: "<<a.size()<<"\n";
		cout<<"中序遍历:  ";
		a.out();cout<<"\n";
	}
	return 0;
}