Splay真心比sbt难调多了QAQ

调一个remove一上午终于搞好了QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define P 1000000
#define MAXINT 100000000000
using namespace std;
struct splay
{
	splay *ch[2],*fa;//ch[0]为左子树ch[1]为右子树fa为父节点 
	int data,cnt,size;//data节点数值cnt重复元素个数size树的大小
}*root,*no;
int ans;
int n,key,flag,pet,human;
void calc(splay *x)
{
	x->size=x->cnt;
	if (x->ch[0]) x->size+=x->ch[0]->size;
	if (x->ch[1]) x->size+=x->ch[1]->size;
}
void rot(splay *x,bool flag)//flag=0左旋flag=1右旋 节省编程复杂度的小优化 
{
	splay *y=x->fa;
	y->ch[!flag]=x->ch[flag];
    if (x->ch[flag]!=NULL) x->ch[flag]->fa=y;
	x->fa=y->fa;
	if (y->fa!=NULL)
	    if (y->fa->ch[0]==y) y->fa->ch[0]=x;
	    else y->fa->ch[1]=x;
	x->ch[flag]=y;
	y->fa=x;
	if (y==root) root=x;
}
void Splay(splay *x,splay *f)//将节点X提到节点f下 (地位与sbt Maintain()相同的操作0-0)
{
	if (x==f||x==NULL) return;
	while (x->fa!=f)
	{
		if (x->fa->fa==f)
		{
			if (x->fa->ch[0]==x) rot(x,1);
		    else rot(x,0);
		}
		else
		{
			splay *y=x->fa,*z=y->fa;
			if (z->ch[0]==y)
			    if (y->ch[0]==x)
			        rot(y,1),rot(x,1);
			    else
			        rot(x,0),rot(x,1);
			else
			    if (y->ch[0]==x)
			        rot(x,1),rot(x,0);
			    else
			        rot(y,0),rot(x,0);
		}
	}
	if (f==NULL) root=x;
	if (x!=NULL)calc(x);
	if (f!=NULL)calc(f);
}
void insert(int data)
{
	splay *n=root,*x=NULL;
	while (n!=NULL)
	{
		x=n;
		if (data>=n->data) n=n->ch[1];
		else n=n->ch[0];
	}
	n=new splay;
	n->ch[0]=n->ch[1]=NULL;
	n->size=1;
	n->data=http://www.mamicode.com/data;>

【HNOI2004】宠物收养所【重做Splay做法】