板子过了,弱化版没过?
查看原帖
板子过了,弱化版没过?
152980
Euclid楼主2021/7/15 15:57

平衡树板子蒯过来,样例过了,题没过?

#include<bits/stdc++.h>
using namespace std;
const int maxn=300005;
int n,root,cnt;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-'){t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*t;
}
struct sm
{
	int val;
	int size;
	int fa,child[2];
	int sum;
}tree[maxn];
void pushup(int x){tree[x].size=tree[tree[x].child[0]].size+tree[tree[x].child[1]].size+tree[x].sum;}
void rotate(int x)
{
	int father=tree[x].fa;
	int grandfather=tree[father].fa;
	int k=(x==tree[father].child[1]);//k=0左子树k=1右子树
	tree[grandfather].child[tree[grandfather].child[1]==father]=x;
	tree[x].fa=grandfather;
	tree[father].child[k]=tree[x].child[k^1];
	tree[tree[x].child[k^1]].fa=father;
	tree[x].child[k^1]=father;
	tree[father].fa=x;
	pushup(father);
	pushup(x);
}
void splay(int x,int goal)
{
	while(tree[x].fa!=goal)
	{
		int father=tree[x].fa;
		int grandfather=tree[father].fa;
		if(grandfather!=goal)(tree[father].child[0]==x)^(tree[grandfather].child[0]==father)?rotate(x):rotate(father);
		rotate(x);
	}
	if(goal==0)root=x;
}
void insert(int x)
{
	int u=root,father=0;
	while(u&&tree[u].val!=x)
	{
		father=u;
		u=tree[u].child[x>tree[u].val];
	}
	if(u)tree[u].sum++;
	else
	{
		u=++cnt;
		if(father)
			tree[father].child[x>tree[father].val]=u;
		tree[u].child[1]=0;
		tree[u].child[0]=0;
		tree[u].val=x;
		tree[u].size=1;
		tree[u].sum=1;
		tree[u].fa=father;
	}
	splay(u,0);

}
void find(int x)
{
	int u=root;
	if(!u)return;
	while(tree[u].child[x>tree[u].val]&&tree[u].val!=x)
		u=tree[u].child[x>tree[u].val];
//	if(tree[u].val!=x)find(-2147483647);
	splay(u,0);
}
int next(int x,int f)//前驱f=0后继=1
{
	find(x);
	int u=root;
	if(tree[u].val>x&&f)return u;
	if(tree[u].val<x&&!f)return u;
	u=tree[u].child[f];
	while(tree[u].child[f^1])u=tree[u].child[f^1];
	return u;
}
void delate(int x)
{

	int q=next(x,0);
	int h=next(x,1);
	splay(q,0);
	splay(h,q);
	int goal=tree[h].child[0];
	if(tree[goal].sum>1)
	{
		tree[goal].sum--;
		splay(goal,0);
	}
	else
		tree[h].child[0]=0;
}
int query(int x)
{

	int u=root;
	if(tree[u].size<x)return 0;
	while(1)
	{
	//	cout<<1<<" ";
		int l=tree[u].child[0];
		if(x>tree[l].size+tree[u].sum)
		{
			x-=tree[l].size+tree[u].sum;
			u=tree[u].child[1];
		}
		else if(tree[l].size>=x)u=l;
		else return tree[u].val;
	}
	//return tree[u].val;
}
int main()
{
	//scanf("%d",&n);
//	freopen("ll.in","r",stdin);
//	freopen("ll.out","w",stdout);
	n=read();
	insert(+2147483647);
    insert(-2147483647);
	for(int i=1;i<=n;i++)
	{
		//scanf("%d%d",&opt,&x);
		int opt=read();
		int x=read();
		if(opt==5)
		{
			insert(x);
		}
		if(opt==1)
		{
			find(x);
			printf("%d\n",tree[tree[root].child[0]].size);
		}
		if(opt==2)
		{
			printf("%d\n",query(x+1));
		}
		if(opt==3)
		{
			printf("%d\n",tree[next(x,0)].val);
		}
		if(opt==4)
		{
			printf("%d\n",tree[next(x,1)].val);
		}
	}
	return 0;
}
2021/7/15 15:57
加载中...