30pts死掉了
查看原帖
30pts死掉了
594755
niweizheni楼主2024/7/12 16:24

#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;
}

一定会谢谢大佬!

2024/7/12 16:24
加载中...