社区讨论
求助,为什么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 条回复,欢迎继续交流。
正在加载回复...