默写splay板子
很多细节问题。。。
#include<cstdio>
#include<iostream>
using namespace std;
#define maxn 1000005
int root;
int tot=;
int ch[maxn][],par[maxn];
int cnt[maxn],size[maxn];
int val[maxn],dat[maxn];
void pushup(int x)
{
size[x]=cnt[x]+size[ch[x][]]+size[ch[x][]];
}///size信息
bool which(int x)
{
return ch[par[x]][]==x;
}
void rotate(int x)
{
int y=par[x],z=par[y];///?
int w=which(x);
int t=ch[x][w^];
par[t]=y;
ch[y][w]=t;
//par[t]=y;
par[x]=z;
ch[z][which(y)]=x;
//par[x]=z;
par[y]=x;
ch[x][w^]=y;
//par[y]=x;
pushup(y);
pushup(x);
}
void splay(int x,int goal=)
{
if(x==)return;
int y,z;
while(par[x]!=goal)///为什么不是x
{
// cout<<"PAR"<<par[x]<<endl;
y=par[x],z=par[y];
//cout<<x<<y<<z<<"YZ"<<endl;
if(z!=goal) ///???
{
if(which(x)==which(y))
{
rotate(y);
}
else rotate(x);
}
rotate(x);
// x=par[x];
// y=par[y];
} if(!goal)root=x;
}
void find(int x)
{
int cur=root;
while(ch[cur][x>val[cur]]&&x!=val[cur])
{
cur=ch[cur][x>val[cur]];
}///为什么不维护父节点了？
splay(cur);
}
int pre(int x)
{
find(x);
int cur=ch[root][];
if(!cur)return ;///直接返回0
//cout<<root<<" pre "<<ch[root][0]<<endl;
while(ch[cur][])
{
cur=ch[cur][];
}
return cur; }
int succ(int x)
{
find(x);
int cur=ch[root][];
if(!cur)return ;
//cout<<root<<" pre "<<ch[root][1]<<endl;
while(ch[cur][])
{
cur=ch[cur][];
}
return cur; }
void dfs(int cur)
{
//cout<<cur<<"cur"<<" ch "<<ch[cur][1]<<endl;
if(ch[cur][])dfs(ch[cur][]);
cout<<val[cur]<<" "<<dat[cur]<<'\n';
if(ch[cur][])dfs(ch[cur][]);
}
void del(int x)
{
//cout<<root<<"END"<<endl;
int p=pre(x),s=succ(x);///后缀为0？？？前驱为0？？？
// cout<<p<<" PS "<<s<<endl; if(!s)
{
if(!p)
{
ch[root][]=ch[root][]=root=;///只有一个点
return;
} splay(p);///没有后缀
ch[root][]=;
return;
}///???
//cout<<x<<endl;
//cout<<p<<s<<endl;
splay(p);
splay(s,p);
int de=ch[s][];
if(cnt[de]>)
{
cnt[de]--;
splay(de);
}
else
ch[s][]=;
//par[ch[root][1]]=root;
//pushup(root); }
void ins(int x,int d)
{
int cur=root,p=;///维护父节点信息
while(cur&&(x!=val[cur]))
{
p=cur;
cur=ch[cur][x>val[cur]];///>号
}
if(cur)
{
cnt[cur]++;
}
else
{
cur=++tot;
//cout<<p<<"父亲"<<endl;
if(p)ch[p][x>val[p]]=cur;///判一下p是否为0
ch[cur][]=ch[cur][]=;
par[cur]=p;///注意维护下父节点
val[cur]=x;
dat[cur]=d;
size[cur]=;
cnt[cur]=;
// dfs(root); splay(cur);
}
// cout<<"DFS"<<endl;
//dfs(root); } int mi()
{
int cur=root;
if(!cur)return ;
while(ch[cur][])
{
cur=ch[cur][];
}
int ans=dat[cur];
del(val[cur]);
return ans;
}
int ma()
{
int cur=root;
if(!cur)return ;
while(ch[cur][])
{
cur=ch[cur][];
}
int ans=dat[cur];
//cout<<ans<<endl;
del(val[cur]);
//dfs(root);
return ans;
}
int main()
{
int n,d,p;
while(scanf("%d",&n)!=EOF)
{
if(n==)break;
else if(n==)
{
scanf("%d%d",&d,&p);
ins(p,d);
}
else if(n==)
{
cout<<ma()<<'\n'; }
else if(n==)
{
cout<<mi()<<'\n';
}
}
}