本文主要是介绍codevs1285 宠物收养所 splayTree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
删除节点时把它移到根节点，把它的后继移到根的右子节点，然后删除根。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define inf 1000000000
using namespace std;
const int maxn=200005;
struct SplayTree
{int son[maxn][2],pre[maxn],val[maxn];int sum[maxn];int rt,sz;void pushUp(int x) {sum[x]=sum[son[x][0]]+sum[son[x][1]]+1;}void newNode(int f,int& x,int a) {x=++sz;pre[x]=f;val[x]=a;sum[x]=1;son[x][0]=son[x][1]=0;}void init() {sz=rt=0;}void Rotate(int x,int c) {int y=pre[x];son[y][!c]=son[x][c];pre[son[x][c]]=y;pre[x]=pre[y];if(pre[x])son[pre[y]][son[pre[y]][1]==y]=x;son[x][c]=y;pre[y]=x;pushUp(y);}void Splay(int x,int goal) {while(pre[x]!=goal) {if(pre[pre[x]]==goal) {if(son[pre[x]][0]==x)Rotate(x,1);elseRotate(x,0);}else {int y=pre[x],z=pre[y];if(son[z][0]==y) {if(son[y][0]==x) {Rotate(y,1);Rotate(x,1);}else {Rotate(x,0);Rotate(x,1);}}else {if(son[y][1]==x) {Rotate(y,0);Rotate(x,0);}else {Rotate(x,1);Rotate(x,0);}}}}pushUp(x);if(goal==0)rt=x;}void Insert(int a) {if(rt==0) {rt=++sz;val[rt]=a;sum[rt]=1;son[rt][0]=son[rt][1]=0;return;}int x=rt;while(son[x][val[x]<a])x=son[x][val[x]<a];newNode(x,son[x][val[x]<a],a);Splay(sz,0);}int getMin(int a) {int Min=inf;int x=rt;while(x) {if(val[x]==a)return a;if(val[x]>a)Min=min(Min,val[x]);if(val[x]>a)x=son[x][0];elsex=son[x][1];}return Min;}int getMax(int a) {int Max=-inf;int x=rt;while(x) {if(val[x]==a) {return a;}if(val[x]<a) {Max=max(Max,val[x]);}if(val[x]<a)x=son[x][1];elsex=son[x][0];}return Max;}int Find(int a) {int x=rt;while(x) {if(val[x]==a)return x;if(val[x]>a)x=son[x][0];elsex=son[x][1];}}void del(int a) {int x=Find(a);Splay(x,0);int tmp=son[x][1];if(tmp==0) {rt=son[rt][0];pre[rt]=0;return;}while(son[tmp][0]) {tmp=son[tmp][0];}Splay(tmp,x);son[tmp][0]=son[rt][0];pre[son[rt][0]]=tmp;rt=tmp;pre[rt]=0;}
}spt;
int mod=1000000;
int n,a,b;
int main()
{spt.init();scanf("%d",&n);int c=0,p=0;int ans=0;while(n--) {scanf("%d%d",&a,&b);if(a==0) {if(p==0) {spt.Insert(b);c++;}else {int mi=spt.getMin(b);int mx=spt.getMax(b);if(abs(mx-b)<=abs(mi-b)) {spt.del(mx);ans=(ans+abs(mx-b))%mod;}else {spt.del(mi);ans=(ans+abs(mi-b))%mod;}p--;}}else {if(c==0) {spt.Insert(b);p++;}else {int mi=spt.getMin(b);int mx=spt.getMax(b);if(abs(mx-b)<=abs(mi-b)) {spt.del(mx);ans=(ans+abs(mx-b))%mod;}else {spt.del(mi);ans=(ans+abs(mi-b))%mod;}c--;}}}printf("%d\n",ans);return 0;
}这篇关于codevs1285 宠物收养所 splayTree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
