社区讨论

有大佬能帮我查错吗?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 条回复,欢迎继续交流。

正在加载回复...