一开始使用了奇怪的ls和rs,之后代码长度直接暴增。。
第一次打平衡树,断断续续调了几天了。
如果码风奇怪请见谅,真心求助,谢谢各位。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{
int ls,rs,fa,v,size,cnt;//左子树,右子树,父亲,节点存的值,子树大小,当前节点有多少个数。
}a[1000005];
int n,q,p,root;
void splay_rotate(int x)
{
int y=a[x].fa;
int z=a[y].fa;
if(a[z].ls==y)a[z].ls=x;
else a[z].rs=x;
a[x].fa=z;
if(a[y].ls==x)
{
a[y].ls=a[x].rs;
a[a[x].rs].fa=y;
a[x].rs=y;
a[y].fa=x;
}
else
{
a[y].rs=a[x].ls;
a[a[x].ls].fa=y;
a[x].ls=y;
a[y].fa=x;
}
a[x].size=a[a[x].ls].size+a[a[x].rs].size+a[x].cnt;
a[y].size=a[a[y].ls].size+a[a[y].rs].size+a[y].cnt;
}
void splay(int x,int to)
{
while(a[x].fa!=to)
{
int y=a[x].fa;
int z=a[y].fa;
if(z!=to)
{
if((a[z].ls==y)==(a[y].ls==x))
{
splay_rotate(y);
splay_rotate(x);
}
else
{
splay_rotate(x);
splay_rotate(x);
}
}
else splay_rotate(x);
}
if(!to)root=x;
}
int splay_find(int x)
{
int u=root;
while(a[u].v!=x)
{
if(a[u].v<u)
{
if(!a[u].rs)break;
u=a[u].rs;
}
else
{
if(!a[u].ls)break;
u=a[u].ls;
}
}
splay(u,0);
return a[a[u].ls].size;
}
int splay_rfind(int x)
{
int u=root;
while(1)
{
if(x<=a[u].cnt+a[a[u].ls].size)
{
if(x>a[a[u].ls].size)return a[u].v;
u=a[u].ls;
}
else
{
x-=(a[u].cnt+a[a[u].ls].size);
u=a[u].rs;
}
}
}
void splay_insert(int x)
{
int u=root;
int father=0;
while(u&&a[u].v!=x)
{
father=u;
if(a[u].v>x)u=a[u].ls;
else u=a[u].rs;
}
if(u)a[u].cnt++;
else
{
u=++n;
if(father)
{
if(a[father].v>x)a[father].ls=u;
else a[father].rs=u;
}
a[u].cnt=1;
a[u].size=1;
a[u].v=x;
a[u].fa=father;
a[u].ls=0;
a[u].rs=0;
}
splay(u,0);
}
int splay_big(int x)
{
splay_find(x);
int u=root;
if(x<a[root].v)return a[root].v;
u=a[root].rs;
while(a[u].ls)u=a[u].ls;
return a[u].v;
}
int splay_small(int x)
{
splay_find(x);
int u=root;
if(x>a[root].v)return a[root].v;
u=a[root].ls;
while(a[u].rs)u=a[u].rs;
return a[u].v;
}
void splay_delete(int x)
{
int last=splay_small(x);
int next=splay_big(x);
splay(last,0);
splay(next,last);
int del=a[next].ls;
if(a[del].cnt>1)
{
a[del].cnt--;
splay(del,0);
}
else a[next].ls=0;
}
int main()
{
splay_insert(0x7fffffff);
splay_insert(-0x7fffffff);
int x,y;
cin>>p;
for(int i=1;i<=p;i++)
{
scanf("%d%d",&x,&y);
if(x==1)splay_insert(y);
else if(x==2)splay_delete(y);
else if(x==3)printf("%d\n",splay_find(y));
else if(x==4)printf("%d\n",splay_rfind(y));
else if(x==5)printf("%d\n",splay_small(y));
else if(x==6)printf("%d\n",splay_big(y));
}
}
(之前有个帖子都沉了)