关于我平衡树为什么会 WA 这档事
查看原帖
关于我平衡树为什么会 WA 这档事
60990
Karry5307Rikka楼主2020/10/15 23:05

rt,从 P3369 蒯过来的能 AC 代码在这里 WA 了/kk,不知道为什么

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=2e5+51,inf=0x3f3f3f3f;
ll n,op,x;
inline ll read()
{
	register ll num=0,neg=1;
	register char ch=getchar();
	while(!isdigit(ch)&&ch!='-')
	{
		ch=getchar();
	}
	if(ch=='-')
	{
		neg=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		num=(num<<3)+(num<<1)+(ch-'0');
		ch=getchar();
	}
	return num*neg;
}
namespace Splay{
	struct Node{
		ll fa,val,sz,tmp;
		ll ch[2];
		inline void reset(ll val=0,ll fa=0)
		{
			this->val=val,this->fa=fa,this->sz=this->tmp=1;
			this->ch[0]=this->ch[1]=0;
		}
	};
	struct Splay{
		ll tot,rt;
		Node nd[MAXN];
		inline ll id(ll x)
		{
			return nd[nd[x].fa].ch[1]==x;
		}
		inline void update(ll x)
		{
			nd[x].sz=nd[nd[x].ch[0]].sz+nd[nd[x].ch[1]].sz+nd[x].tmp;
		}
		inline void connect(ll x,ll fa,ll dir)
		{
			nd[x].fa=fa,nd[fa].ch[dir]=x;
		}
		inline void rotate(ll x)
		{
			ll fa=nd[x].fa,gfa=nd[fa].fa,dir=id(x);
			connect(x,gfa,id(fa));
			connect(nd[x].ch[dir^1],fa,dir);
			connect(fa,x,dir^1);
			update(fa),update(x);
		}
		inline void splay(ll cur,ll target)
		{
			while(nd[cur].fa!=target)
			{
				ll fa=nd[cur].fa,gfa=nd[fa].fa;
				if(gfa!=target)
				{
					rotate(id(cur)^id(fa)?cur:fa);
				}
				rotate(cur);
			}
			rt=target?rt:cur;
		}
		inline void insert(ll val)
		{
			ll x=rt,fa=0;
			while(x&&nd[x].val!=val)
			{
				fa=x,x=nd[x].ch[val>nd[x].val];
			}
			if(x)
			{
				nd[x].tmp++;
			}
			else
			{
				x=++tot;
				if(fa)
				{
					nd[fa].ch[val>nd[fa].val]=x;
				}
				nd[x].reset(val,fa);
			}
			splay(x,0);
		}
		inline void find(ll val)
		{
			ll x=rt;
			if(!x)
			{
				return;
			}
			while(nd[x].ch[val>nd[x].val]&&nd[x].val!=val)
			{
				x=nd[x].ch[val>nd[x].val];
			}
			splay(x,0);
		}
		inline ll getPrev(ll val)
		{
			find(val);
			ll x=rt;
			if(nd[x].val<val)
			{
				return x;
			}
			x=nd[x].ch[0];
			while(nd[x].ch[1])
			{
				x=nd[x].ch[1];
			}
			return x;
		}
		inline ll getNext(ll val)
		{
			find(val);
			ll x=rt;
			if(nd[x].val>val)
			{
				return x;
			}
			x=nd[x].ch[1];
			while(nd[x].ch[0])
			{
				x=nd[x].ch[0];
			}
			return x;
		}
		inline ll prev(ll val)
		{
			return nd[getPrev(x)].val;
		}
		inline ll next(ll val)
		{
			return nd[getNext(x)].val;
		}
		inline void del(ll val)
		{
			ll prv=getPrev(val),nxt=getNext(val),ls;
			splay(prv,0),splay(nxt,prv),ls=nd[nxt].ch[0];
			if(nd[ls].tmp>1)
			{
				nd[ls].tmp--,splay(ls,0);
			}
			else
			{
				nd[nxt].ch[0]=0;
			}
		}
		inline ll findRank(ll val)
		{
			return find(val),nd[nd[rt].ch[0]].sz;
		}
		inline ll findVal(ll rk)
		{
			ll x=rt,ls;
			if(nd[rt].sz<rk)
			{
				return 0;
			}
			while(1)
			{
				ls=nd[x].ch[0];
				if(rk>nd[ls].sz+nd[x].tmp)
				{
					rk-=nd[ls].sz+nd[x].tmp,x=nd[x].ch[1];
				}
				else
				{
					if(rk<=nd[ls].sz)
					{
						x=ls;
					}
					else
					{
						return nd[x].val;
					}
				}
			}
		}
	};
}
Splay::Splay splay;
int main()
{
	splay.insert(inf),splay.insert(-inf),n=read();
	for(register int i=0;i<n;i++)
	{
		op=read(),x=read();
		if(op==1)
		{
			printf("%d\n",splay.findRank(x));
		}
		if(op==2)
		{
			printf("%d\n",splay.findVal(x+1));
		}
		if(op==3)
		{
			printf("%d\n",splay.prev(x));
		}
		if(op==4)
		{
			printf("%d\n",splay.next(x));
		}
        if(op==5)
		{
			splay.insert(x);
		}
	}
}
2020/10/15 23:05
加载中...