40分treap树求调6-11WA12T
查看原帖
40分treap树求调6-11WA12T
109615
242424hyb楼主2022/10/26 15:20

不知道哪错了 求调

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0')
	{
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int n,opt,x,inf=1<<30;
struct node 
{
	int key,rank,size,cnt;
	node *son[2];
	bool operator <(const node a)const{return rank<a.rank;}
	int cmp(int x)const
	{
		if(key==x)return -1;
		return x<key?0:1;
	}
	void update()
	{
		size=cnt;
		if(son[0]!=NULL)size+=son[0]->size;
		if(son[1]!=NULL)size+=son[1]->size; 
	} 
};
void rotate(node *&o,int d)//转
{
	node *k=o->son[d^1];
	o->son[d^1]=k->son[d];
	k->son[d]=o;
	o->update();
	k->update();
	o=k;
}
void insert(node *&o,int k)//插入节点
{
	if(o==NULL)
	{
		o=new node();
		o->son[0]=o->son[1]=NULL;
		o->rank=rand();
		o->key=k;
		o->size=1;
		o->cnt=1;
	}
	else if(o->key==k)
	{
		o->cnt++;
	}
	else 
	{
		int d=o->cmp(k);
		insert(o->son[d],k);
		if(o<o->son[d])rotate(o,d^1);
	}
	o->update();
}
void remove(node *&o,int k)//删节点
{
	int d=o->cmp(k);
	if(d==-1)
	{
		if(o->cnt>1)
		{
			o->cnt--;
			o->update();
			return ;
		}
		else
		{
			node *x=o;
			if(o->son[0]!=NULL&&o->son[1]!=NULL){
				int d1=o->son[1]->rank<o->son[0]->rank?1:0;
				rotate(o,d1);
				remove(o->son[d1],k);
			}
			else{
				if(o->son[0]==NULL)o=o->son[1];
				else o=o->son[0];
				delete x;
			}
		}
	}else remove(o->son[d],k);
	if(o!=NULL)o->update();
}
int kth(node *o,int k)//找第k个
{
	if(o==NULL||k<=0||k>o->size)return -1;
	int x=o->son[0]==NULL?0:o->son[0]->size;
	if(x+1<=k&&x+o->cnt>=k)return o->key;
	if(k<=x)return kth(o->son[0],k);
	else return kth(o->son[1],k-o->cnt-x);
}
int find(node *o,int k)找k是第几个
{
	if(o==NULL)return -1; 
	int d=o->cmp(k);
	if(d==-1){
		return o->son[0]==NULL?1:1+o->son[0]->size;
	}
	if(d==0)return find(o->son[0],k);
	else {
		int t=find(o->son[1],k);
		if(t==-1)return -1;
		return o->son[0]==NULL?t+o->cnt:t+o->cnt+o->son[0]->size;
	}
}
int fpre(node *o,int k)//前驱
{
	int pre=-inf;
	while(o!=NULL)
	{
		if(o->key>=k)o=o->son[0];
		else{
			pre=o->key;
			o=o->son[1];
		}
	}
	return pre;
}
int fnxt(node *o,int k)//后驱
{
	int nxt=inf;
	while(o!=NULL)
	{
		if(o->key<=k)o=o->son[1];
		else{
			nxt=o->key;
			o=o->son[0];
		}
	}
	return nxt;
}
int main()
{
	n=read();
	node *root=new node();
	for(int i=1;i<=n;i++)
	{
		opt=read();
		x=read();
		if(opt==1)insert(root,x);
		if(opt==2)remove(root,x);
		if(opt==3){
			printf("%d\n",find(root,x));
		}
		if(opt==4){
			printf("%d\n",kth(root,x));
		}
		if(opt==5)printf("%d\n",fpre(root,x));
		if(opt==6)printf("%d\n",fnxt(root,x));
	}
	return 0;
}

好像是很多输出1的地方我输出0了,但不知道为什么

2022/10/26 15:20
加载中...