How Splay

void insert(ll sum){
			if(root==NULL){
				root=new Splay_Node(sum);
				return;
			}
			Splay_Node* lrt=lower_bound(sum);
			if(lrt!=NULL&&lrt->sum==sum){
				lrt->self_siz++;
				update(lrt);
				return;
			}
			Splay_Node* rrt=upper_bound(sum);
			splay(lrt,root);
			splay(rrt,lrt);
			Splay_Node* newnode=new Splay_Node(sum);
			rrt->ls=newnode;
			newnode->fa=rrt;
			update(rrt);
			update(lrt);
		}

struct Splay{
		struct Splay_Node{
			ll sum;
			int siz, self_siz;
			Splay_Node* ls;
			Splay_Node* rs;
			Splay_Node* fa;
			Splay_Node(ll _sum) : siz(1), self_siz(1), ls(NULL), rs(NULL), fa(NULL) { sum=_sum; }
		};
		Splay_Node* root;
		Splay() : root(NULL) {}
		void update(Splay_Node* &rt){
			if(rt!=NULL){
				rt->siz=rt->self_siz;
				if(rt->ls!=NULL) rt->siz+=rt->ls->siz;
				if(rt->rs!=NULL) rt->siz+=rt->rs->siz;
			}
		}
		int get(Splay_Node* rt){
			return rt->fa->rs==rt;
		}
		void rotate(Splay_Node* rt){
			Splay_Node* f=rt->fa;
			Splay_Node* g=f->fa;
			if(get(rt)){
				f->rs=rt->ls;
				if(f->rs!=NULL) f->rs->fa=f;
				rt->ls=f;
			}else{
				f->ls=rt->rs;
				if(f->ls!=NULL) f->ls->fa=f;
				rt->rs=f;
			}
			f->fa=rt;
			rt->fa=g;
			if(g!=NULL){
				if(g->rs==f) g->rs=rt;
				else g->ls=rt;
			}
			update(f);
			update(rt);
		}
		void splay(Splay_Node* rt,Splay_Node* to){
			if(rt==NULL) return;
			if(to==NULL) root=rt;
			while(1){
				Splay_Node* f=rt->fa;
				Splay_Node* g=f->fa;
				if(f==to) break;
				if(g!=to){
					if(get(rt)==get(f)) rotate(f);
					else rotate(rt);
				}
				rotate(rt);
			}
			update(rt);
		}
		Splay_Node* build(int dl,int dr,Splay_Node* fa,ll *arr){//You need to ensure that the array is sorted.
			if(dr>dl) return NULL;
			int mid=(dl+dr)>>1;
			Splay_Node* newnode=new Splay_Node(arr[mid]);
			newnode->fa=fa;
			newnode->ls=build(dl,mid-1,newnode,arr);
			newnode->rs=build(mid+1,dr,newnode,arr);
			update(newnode);
			return newnode;
		}
		void clear(Splay_Node* rt){
			if(rt==NULL) return;
			clear(rt->ls);
			clear(rt->rs);
			delete rt;
		}
		Splay_Node* merge(Splay_Node* rt1,Splay_Node* rt2){
			if(rt1==NULL&&rt2==NULL) return NULL;
			if(rt1==NULL) return rt2;
			if(rt2==NULL) return rt1;
			splay(rt2,root);
			rt2->ls=rt1;
			rt1->fa=rt2;
			update(rt2);
			return rt2;
		}
		Splay_Node* kth(int k){
			Splay_Node* nw=root;
			while(1){
				if(nw==NULL) return NULL;
				if(nw->ls!=NULL&&k<=nw->ls->siz) nw=nw->ls;
				else{
					int tp=((nw->ls!=NULL)?(nw->ls->siz):(0))+nw->self_siz;
					if(k<=tp) return nw;
					k-=tp,nw=nw->rs;
				}
			}
		}
		int rk(ll sum){
			Splay_Node* nw=root;
			int ans=1;
			while(1){
				if(nw==NULL) return -1;
				if(sum<nw->sum) nw=nw->ls;
				else{
					ans+=((nw->ls!=NULL)?(nw->ls->siz):(0));
					if(sum==nw->sum){
						splay(nw,root);
						return ans;
					}
					ans+=nw->self_siz;
					nw=nw->rs;
				}
			}
		}
		Splay_Node* lower_bound(ll sum){
			Splay_Node* nw=root;
			Splay_Node* ans=NULL;
			while(nw!=NULL){
				if(sum<=nw->sum) ans=nw,nw=nw->ls;
				else nw=nw->rs;
			}
			if(ans!=NULL) splay(ans,root);
			return ans;
		}
		Splay_Node* upper_bound(ll sum){
			Splay_Node* nw=root;
			Splay_Node* ans=NULL;
			while(nw!=NULL){
				if(sum<nw->sum) ans=nw,nw=nw->ls;
				else nw=nw->rs;
			}
			if(ans!=NULL) splay(ans,root);
			return ans;
		}
		void insert(int bg,int len,ll* arr){//不支持增加至已存在的节点
			Splay_Node* lrt=kth(bg);
			Splay_Node* rrt=kth(bg+1);
			splay(lrt,root);
			splay(rrt,lrt);
			rrt->ls=build(1,len,rrt,arr);
			update(rrt);
			update(lrt);
		}
		void insert(ll sum){
			if(root==NULL){
				root=new Splay_Node(sum);
				return;
			}
			Splay_Node* lrt=lower_bound(sum);
			if(lrt!=NULL&&lrt->sum==sum){
				lrt->self_siz++;
				update(lrt);
				return;
			}
			Splay_Node* rrt=upper_bound(sum);
			splay(lrt,root);
			splay(rrt,lrt);
			Splay_Node* newnode=new Splay_Node(sum);
			rrt->ls=newnode;
			newnode->fa=rrt;
			update(rrt);
			update(lrt);
		}
		void erase(int bg,int ed){//全部删除区间内节点
			Splay_Node* lrt=kth(bg);
			Splay_Node* rrt=kth(ed+1);
			splay(lrt,0);
			splay(rrt,lrt);
			clear(rrt->ls);
			update(rrt);
			update(lrt);
		}
		void erase(ll sum){
			Splay_Node* rt=lower_bound(sum);
			if(rt!=NULL||rt->sum!=sum) return;
			splay(rt,root);
			rt->self_siz--;
			if(rt->self_siz>0){
				update(rt);
				return;
			}
			Splay_Node* lrt=rt->ls;
			Splay_Node* rrt=rt->rs;
			if(lrt!=NULL) lrt->fa=NULL;
			if(rrt!=NULL) rrt->fa=NULL;
			root=merge(lrt,rrt);
		}
		ll precursor(Splay_Node* rt,ll sum){
			if(rt==NULL) return 0;
			if(rt->sum>=sum) return precursor(rt->ls,sum);
			ll rsum=precursor(rt->rs,sum);
			if(!rsum) return rt->sum;
			return rsum;
		}
		ll precursor(ll sum){
			return precursor(root,sum);
		}
		ll successor(Splay_Node* rt,ll sum){
			if(rt==NULL) return 0;
			if(rt->sum<=sum) return successor(rt->rs,sum);
			ll lsum=successor(rt->ls,sum);
			if(!lsum) return rt->sum;
			return lsum;
		}
		ll successor(ll sum){
			return successor(root,sum);
		}
		void inorder(Splay_Node* rt){
			if(rt==NULL) return;
			inorder(rt->ls);
			for(int i=1;i<=rt->self_siz;i++) O rt->sum;
			inorder(rt->rs);
		}
		void inorder(){
			inorder(root);
		}
	};