求大佬找不同,悬1关
查看原帖
求大佬找不同,悬1关
1162380
liverxiwo楼主2024/4/22 12:56

这注释部分和底下的有什么不同吗,思路一样的fhq我是真不理解为啥注释部分不能ac底下就可以

#include<bits/stdc++.h>
int root=0,tot=0;
struct FHQ_treap{
	struct fhq_treap{
		int l,r,val,siz,dat;
	}tree[500005];
	inline void update(int x){
		tree[x].siz=tree[tree[x].l].siz+tree[tree[x].r].siz+1;
		return ;
	}
	inline int newnode(int x){
		tree[++tot].val=x;
		tree[tot].siz=1;
		tree[tot].dat=rand();
		return tot;
	}
	inline void split(int k,int key,int &x,int &y){
		if(k==0){
			x=y=0;
			return ;
		}
		if(tree[k].val<=key){
			x=k;
			split(tree[x].r,key,tree[x].r,y);
		}
		else{
			y=k;
			split(tree[y].l,key,x,tree[y].l);
		}
		update(k);
		return ;
	}
	inline int merge(int x,int y){
		if(x==0){
			return y;
		}
		if(y==0){
			return x;
		}
		if(tree[x].dat>tree[y].dat){
			tree[x].r=merge(tree[x].r,y);
			update(x);
			return x;
		}
		else{
			tree[y].l=merge(x,tree[y].l);
			update(y);
			return y;
		}
	}
	//bug on last
	/*void insert(int key){
		int x,y;
		split(root,key-1,x,y);
		int id=newnode(key);
		root=merge(merge(x,id),y);
		return ;
	}
	void remove(int key){
		int x,y,z;
		split(root,key-1,x,y);
		split(y,key,y,z);
		if(y){
			y=merge(tree[y].l,tree[y].r);
		}
		root=merge(merge(x,z),y);
		return ;
	}
	int rnk(int key){
		int x,y,ans;
		split(root,key-1,x,y);
		ans=tree[x].siz+1;
		root=merge(x,y);
		return ans;
	}
	int kth(int rnk){
		int p=root;
		while(1){
			if(tree[tree[p].l].siz+1==rnk){
				break;
			}
			else if(tree[tree[p].l].siz+1>rnk){
				p=tree[p].l;
			}
			else{
				rnk-=tree[tree[p].l].siz+1;
				p=tree[p].l;
			}
		}
		return tree[p].val;
	}
	int pre(int key){
		int x,y,p;
		split(root,key-1,x,y);
		p=x;
		while(tree[p].r!=0){
			p=tree[p].r;
		}
		root=merge(x,y);
		return tree[p].val;
	}
    int next(int key){
		int x,y,p;
		split(root,key-1,x,y);
		p=y;
		while(tree[p].l!=0){
			p=tree[p].l;
		}
		root=merge(x,y);
		return tree[p].val;
	}*/
	void insert(int key) { //插入键值为key的数 
		int x, y;
		split(root, key - 1, x, y); //把小于等于key-1的分给x 大于等于key的分给y 
		int id = newnode(key);
		root = merge(merge(x, id), y); //把新节点插入到x,y之间 
	}
	
	void remove(int key) { //删除一个键值为key的数 
		int x, y, z;
		split(root, key - 1, x, y); //把小于等于key-1的分给x
		split(y, key, y, z); //把大于key的分给z 那y中就全是等于key的了
		if (y) y = merge(tree[y].l, tree[y].r); //因为只需要删除一个数 所以把根节点删掉左右俩儿子合并
		root = merge(merge(x, y), z); //然后重新合起来 如果要把权值为key的全删掉就把xz合起来 
	}
	
	int rnk(int key) { //查询key的排名 
		int x, y, ans;
		split(root, key - 1, x, y); //把小于key的数都分给x 那么siz[x]就是小于key的数的数量
		ans = tree[x].siz + 1;
		root = merge(x, y); //掰完记得合起来 
		return ans; 
	}
	
	int kth(int rnk) { //查询排名为rnk的数 
		int p = root;
		while (p) {
			if (tree[tree[p].l].siz + 1 == rnk) break; //正正好好查到
			else if (tree[tree[p].l].siz + 1 > rnk) p = tree[p].l; //查过头了
			else {
				rnk -= tree[tree[p].l].siz + 1;
				p = tree[p].r; //还不够 
			} 
		}
		return tree[p].val;
	}
	
	int pre(int key) { //查询key的前驱 
		int x, y, p;
		split(root, key - 1, x, y); //把比key小的都分给x 
		p = x;
		while (tree[p].r != 0) p = tree[p].r; //一直往大的方向走
		root = merge(x, y);
		return tree[p].val; 
	}
	
	int next(int key) { //查询key的后缀 
		int x, y, p;
		split(root, key, x, y); //把比key大的都分给y
		p = y;
		while (tree[p].l != 0) p = tree[p].l;
		root = merge(x, y);
		return tree[p].val; 
	}
}treap;
int n;
int main(){
	srand(time(0));
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int opt,x;
		scanf("%d%d",&opt,&x);
		if(opt==1){
			treap.insert(x);
		}
		else if(opt==2){
			treap.remove(x);
		}
		else if(opt==3){
			printf("%d\n",treap.rnk(x));
		}
		else if(opt==4){
			printf("%d\n",treap.kth(x));
		}
		else if(opt==5){
			printf("%d\n",treap.pre(x));
		}
		else{
			printf("%d\n",treap.next(x));
		}
	}
}
2024/4/22 12:56
加载中...