#1 #2 #19 #20 AC了,其他全是wa
大佬看看为什么?
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+15;
int n,tot=0,root=0;
struct Node
{
int child[2];//左右儿子
int val;//节点的值
int fa;//父亲
int size;//子树大小
int cnt;//节点表示值的个数
}t[N];//平衡树上节点
inline void push_up(int u)//向上推
{
t[u].size=t[t[u].child[0]].size+t[t[u].child[1]].size+t[u].cnt;//两个儿子的数值相加=父亲
}
inline void rotate(int x)//旋转操作(x是要旋上到根的数)
{
int y=t[x].fa;//y是x的父亲
int z=t[y].fa;//z是y的父亲 (x的祖父)
int k=(t[y].child[1]==x);//x是y的左儿子(0)还是右儿子(0)
//把x旋为z的儿子
t[z].child[t[z].child[1]==y]=x;//z的儿子变为x
t[x].fa=z;//x的父亲变为z
//把x的儿子交给y
t[y].child[k]=t[x].child[k^1];//x的左/右儿子变为y的右/左儿子
t[t[x].child[k^1]].fa=y;//x儿子的父亲变为y
//把x的儿子变成y
t[x].child[k^1]=y;//y变为x的相反儿子
t[y].fa=x;//y的父亲变为x
push_up(y);//更新子节点值
push_up(x);
}
inline void splay(int x,int goal)//旋转操作,把x变为goal的儿子
{
while(t[x].fa !=goal)//如果x的父亲不是goal
{
int y=t[x].fa;//y是x的父亲
int z=t[y].fa;//z是y的父亲 (x的祖父)
if(z!=goal)//如果z不是goal
{
(t[y].child[0]==x)^(t[z].child[0]==y)?rotate(x):rotate(y);
//如果x和y同为左儿子或者右儿子先旋转y
//如果x和y不同为左儿子或者右儿子先旋转x
//如果不双旋的话,旋转完成之后树的结构不会变化
}
rotate(x);//把x旋转到z的位置
}
if(goal==0)//如果父亲为0
{
root=x;//那么x旋转到根节点
}
}
//插入操作
inline void Insert(int x)//插入x
{
int u=root;//根节点
int ff=0;//父亲节点
while(u&&t[u].val!=x)//如果u有值且不为x
{
ff=u;
u=t[u].child[x>t[u].val];//向下找左/右儿子
}
if(u)//如果存在这一个点
{
t[u].cnt++;//这一点的数字表示的个数+1
}
else//不存在
{
u=++tot;//新建点
if(ff)//如果父亲是根
{
t[ff].child[t[ff].val<x]=u;//为父亲的左/右儿子
}
t[u].child[0]=0;
t[u].child[1]=0;//节点的孩子初始化为0
t[tot].fa=ff;//初始化父亲
t[tot].val=x;//赋值
t[tot].cnt=1;//数量为一
t[tot].size=1;//字数为一(只有自己一个点)
}
splay(u,0);//把u旋转到根
}
inline void Find(int x)
{
int u=root;
if(!u)
{
return;
}
while(t[u].child[x>t[u].val]&&x!=t[u].val)
{
u=t[u].child[x>t[u].val];
}
splay(u,0);
}
inline int Next(int x,int f)//查找x的前驱(0)或者后继(1)
{
Find(x);
int u=root;//根节点,此时x的父节点(存在的话)就是根节点
if(t[u].val>x&&f)return u;//如果当前节点的值大于x并且要查找的是后继
if(t[u].val<x&&!f)return u;//如果当前节点的值小于x并且要查找的是前驱
u=t[u].child[f];//查找后继的话在右儿子上找,前驱在左儿子上找
while(t[u].child[f^1])u=t[u].child[f^1];//要反着跳转,否则会越来越大(越来越小)
return u;//返回位置
}
inline void Delete(int x)//删除x
{
int last=Next(x,0);//查找x的前驱
int next=Next(x,1);//查找x的后继
splay(last,0);//将前驱旋转到根节点,后继旋转到根节点下面
splay(next,last);//很明显,此时后继是前驱的右儿子,x是后继的左儿子,并且x是叶子节点
int del=t[next].child[0];//后继的左儿子
if(t[del].cnt>1)//如果有多个点
{
t[del].cnt--;//直接减少一个
splay(del,0);//旋转
}
else
{
t[next].child[0]=0;//这个点直接丢掉
}
}
inline int kth(int x)
{
int u=root;
if(t[u].size<x)
{
return 0;
}
for(;;)
{
int y=t[u].child[0];
if(x>t[y].size+t[u].cnt)
{
x-=t[y].size+t[u].cnt;
u=t[u].child[1];
}
else
{
if(t[y].size>=x)
{
u=y;
}
else
{
return t[u].val;
}
}
}
}
int main()
{
cin>>n;//输入n
Insert(+2147483647);//哨兵节点*2
Insert(-2147483647);
for(int i=1;i<=n;i++)
{
int op;
cin>>op;
if(op==1)
{
int x;
cin>>x;
Insert(x);//执行插入操作
}
if(op==2)
{
int x;
cin>>x;
Delete(x);//执行删除操作
}
if(op==3)
{
int x;
cin>>x;
Insert(x);//插入x
Find(x);//寻找x
cout<<t[t[root].child[0]].size<<endl;//输出x的排名
Delete(x);//删除x
}
if(op==4)
{
int x;
cout<<kth(x+1)<<endl;//查询排名为x的数
}
if(op==5)
{
int x;
cout<<t[Next(x,0)].val<<endl;//输出x的前驱
}
if(op==6)
{
int x;
cout<<t[Next(x,1)].val<<endl;//输出x的后继
}
}
return 0;
}
一定会谢谢大佬!