社区讨论
有大佬能帮我查错吗?WA一周了。。。。
P3369【模板】普通平衡树参与者 3已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mi86dmtq
- 此快照首次捕获于
- 2025/11/21 09:22 4 个月前
- 此快照最后确认于
- 2025/11/21 09:22 4 个月前
C
inline int identify(int x){//验证该节点是左儿子还是右儿子
return son[fa[x]][0]==x ? 0 : 1;
}
inline void connect(int x,int f,int iden) {
fa[x]=f;
son[f][iden]=x;
}
inline void update(int x){
size[x]=cnt[x]+size[son[x][0]]+size[son[x][1]];
}
inline int createpoints(int x,int f){
n++;
key[n]=x;
fa[n]=f;
cnt[n]=1;
size[n]=1;
return n;
}
void rotate(int x){
int y=fa[x];
int mroot=fa[y];
int mrootson=identify(y);
int yson=identify(x);
int id=son[x][yson^1];
connect(id,y,yson);
connect(y,x,(yson^1));
connect(x,mroot,mrootson);
update(y);
update(x);
}
int build(int x){
sz++;
if(n==0){
root=1;
createpoints(x,0);
son[0][1]=n;
}
else{
int now=root;
while(1){
size[now]++;
if(x==key[now]){
cnt[now]++;
return now;
}
int nxt=x<key[now] ? 0 : 1;
if(!son[now][nxt]){
createpoints(x,now);
son[now][nxt]=n;
return n;
}
now=son[now][nxt];
}
}
return 0;
}
void splay(int now,int to){
to=fa[to];//需要将now节点旋转到to的父亲节点下
while(fa[now]!=to){
int up=fa[now];
if(fa[up]==to)//当只有一步到达目标时,只用旋转一次即可到达根节点
rotate(now);
else if(identify(now)==identify(up)){//当父亲节点和儿子节点作为儿子位置相同时
rotate(up);
rotate(now);
}
else{//相反时
rotate(now);
rotate(now);
}
}
}
int findx(int val){
int now=root;
while(1){
if(key[now]==val){
splay(now,root);//查找到后需要将该节点旋转到根,来保证树的结构随机性
return now;
}
int nxt=val<key[now] ? 0 : 1;//判断下一步往哪走
if(!son[now][nxt])//如果走到头了,结束
return 0;
now=son[now][nxt];//往下走
}
}
void push(int x){
int add=build(x);
splay(add,root);//保证结构的随机性
}
inline void clear(int x){//清除x节点
son[x][0]=son[x][1]=fa[x]=size[x]=cnt[x]=key[x]=0;//一定得删干净了哈
if(x==n)
n--;//节点数-1
}
void pop(int x){
}
int test(){
queue <int> Q;
Q.push(root);
while(!Q.empty()){
int x=Q.front();
Q.pop();
printf("%d\n",key[x]);
if(son[x][0])
Q.push(son[x][0]);
if(son[x][1])
Q.push(son[x][1]);
}
}
int rank(int val){//获取值为val的排名
int ans=0,now=root;//ans记录在前面的元素
while(1){
if(!now)
return 0;
if(key[now]==val)//找到了
return ans+size[son[now][0]]+1;//返回之前的元素以及当前位置左子树的个数再加上本身1个即为排名
if(val<key[now]){//如果值小于当前节点的值
now=son[now][0];//进入当前节点的左子树
}
else{
ans=ans+size[son[now][0]]+cnt[now];//加上左子树以及当前节点中小于查询值的个数
now=son[now][1];//进入右子树
}
}
}
int atrank(int x){
if(x>sz)
return -1;
int now=root;
while(1){
int minused=size[now]-size[son[now][1]];//左子树加上该节点的元素个数
if(x>size[son[now][0]] && x<=minused)
break;
if(x<minused)
now=son[now][0];
else{
x-=minused;
now=son[now][1];
}
}
splay(now,root);
return key[now];
}
int upper(int val){//找最小的大于x的数
int now=root;
int result=0x7fffffff;
while(now){
if(key[now]>val && key[now]<result)
result=key[now];
if(val<key[now])//选择进哪一棵树
now=son[now][0];
else
now=son[now][1];
}
return result;
}
int lower(int val){//找最大的小于x的数
int now=root;
int result=-0x7ffffffff;
while(now){
if(key[now]<val && key[now]>result)
result=key[now];
if(val>key[now])//选择进哪一棵树
now=son[now][1];
else
now=son[now][0];
}
return result;
}
int main(){
freopen("C://Users//User//Desktop//GG.in","r",stdin);
int m,opt,num;
scanf("%d",&m);
while(m--){
scanf("%d %d",&opt,&num);
switch (opt){
case 1: push(num); break;
case 2: pop(num); break;
case 3: printf("%d\n",rank(num));break;
case 4: printf("%d\n",atrank(num));break;
case 5: printf("%d\n",lower(num));break;
case 6: printf("%d\n",upper(num));break;
}
root=son[0][1];
// test();
// cout<<endl;
}
return 0;
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...