社区讨论

求助,为什么RE

学术版参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi7yjyi4
此快照首次捕获于
2025/11/21 05:43
4 个月前
此快照最后确认于
2025/11/21 05:43
4 个月前
查看原帖
RT,希望哪位大佬能帮我看看我的Treap为啥会RE(目前排查可能是update()跑不了),谢谢!
CPP
#include<bits/stdc++.h>
#define ok cout<<"ok"<<endl;
using namespace std;
const int N=100005;
struct node;
node *nul,*root;
struct node
{
	node *ch[2];
	int r,v,s;
	node()
	{
		ch[0]=nul;
		ch[1]=nul;
		s=0;
	}
	int cmp(int x) const
	{
		if(x==v) return -1;
		return v<x;
	}
	void update()
	{
		s=1;
		s+=ch[0]->s;
		s+=ch[1]->s;
	}
};
void rotate(node* &o,int d)
{
	node *k=o->ch[d^1];
	o->ch[d^1]=k->ch[d];
	k->ch[d]=o;
	o->update();
	k->update();
	o=k;
}
void insert(node* &o,int x)
{
	printf("---in\n");
	if(o==nul)
	{
		o=new node();
		o->r=rand(); o->v=x;
	}
	else
	{
		int d=o->cmp(x);
		insert(o->ch[d],x);
		if(o->ch[d]->r>o->r) rotate(o,d^1);
	}
	o->update();printf("---out\n");
}
void remove(node* &o,int x)
{
	int d=o->cmp(x);
	if(d==-1)
	{
		if(o->ch[0]==nul) o=o->ch[0]; else
		if(o->ch[1]==nul) o=o->ch[1]; 
		else
		{
			int d2=o->ch[0]->r>o->ch[1]->r;
			rotate(o,d2);
			remove(o->ch[d2],x);
		}
	}
	else remove(o->ch[d],x);
	o->update();
}
int kth(node *o,int k)
{
	if(o==nul || k<=0 || k>o->s) return 0;
	int s=o->ch[0]==nul?0:o->ch[0]->s;
	if(k==s+1) return o->v;
	if(k<=s) return kth(o->ch[0],k);
	return kth(o->ch[1],k-s-1);
}
int rank(node *o,int x)
{
	if(o==nul) return 0;
	int k=o->cmp(x);
	if(k==-1) return 1;
	if(!k) return rank(o->ch[0],x);
	return rank(o->ch[1],x)+o->ch[0]->s+1;
}
int n;
int main()
{
	srand((unsigned)time(NULL));
	scanf("%d",&n);
	root->update();
	while(n--)
	{
		int opt,x;
		scanf("%d%d",&opt,&x);
		switch(opt)
		{
			case 1:
				insert(root,x);
				break;
			case 2:
				remove(root,x);
				break;
			case 3:
				printf("%d\n",rank(root,x));
				break;
			case 4:
				printf("%d\n",kth(root,x));
				break;
			case 5:
				printf("%d\n",kth(root,rank(root,x)-1));
				break;
			case 6:
				printf("%d\n",kth(root,rank(root,x)+1));
				break; 
		}
	}
	return 0;
}
请自行忽略Debug语句

回复

2 条回复,欢迎继续交流。

正在加载回复...