FHQTreap,21分求调
查看原帖
FHQTreap,21分求调
710862
thrX楼主2024/7/11 16:02

课上写的,不知道错在哪里,求各位巨佬指教

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=114514;
struct node{
	int l,r,val,rnd,size;
}tr[maxn];
int root,idx;
void newnode(int &x,int v){
	idx++,x=idx,tr[x].val=v,tr[x].rnd=rand(),tr[x].size=1;
}
void pushup(int p){
	tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+1;
}
void split(int p,int v,int &x,int &y){ 
	if(!p){
		x=y=0;
		return;
	}
	if(tr[p].val<v){
		x=p;
		split(tr[p].r,v,tr[p].r,y);
	}else{
		y=p;
		split(tr[p].l,v,x,tr[p].l);
	}
	pushup(p);
}
int merge(int x,int y){ 
	if(!x||!y)return x+y;
	if(tr[x].rnd<tr[y].rnd){
		tr[x].r=merge(tr[x].r,y);
		pushup(x);
		return x;
	}else{
		tr[y].l=merge(x,tr[y].l);
		pushup(y);
		return y;
	}
}
void insert(int v){
	int x,y,z;
	newnode(z,v);
	split(root,v,x,y);
	root=merge(merge(x,z),y);
}
void del(int v){
	int x,y,z;
	split(root,v,x,z);
	split(x,v-1,x,y);
	y=merge(tr[y].l,tr[y].r);
	root=merge(merge(x,y),z);
}
int getrank(int v){
	int x,y;
	split(root,v-1,x,y);
	int ans=tr[x].size+1;
	root=merge(x,y);
	return ans;
}
int getval(int root,int k){
	if(k==tr[tr[root].l].size+1)return tr[root].val;
	if(k<=tr[tr[root].l].size)return getval(tr[root].l,k);
	return getval(tr[root].r,k-tr[tr[root].l].size-1);
}
int getpre(int v){
	int x,y,s,ans;
	split(root,v-1,x,y);
	s=tr[x].size;
	ans=getval(x,s);
	root=merge(x,y);
	return ans;
}
int getnxt(int v){
	int x,y,ans;
	split(root,v,x,y);
	ans=getval(y,1);
	root=merge(x,y);
	return ans;
}
signed main(){
	
	int n,op,v;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>op>>v;
		if(op==1)insert(v);
		else if(op==2)del(v);
		else if(op==3)cout<<getrank(v)<<'\n';
		else if(op==4)cout<<getval(root,v)<<'\n';
		else if(op==5)cout<<getpre(v)<<'\n';
		else cout<<getnxt(v)<<'\n';
	}
	
	return 0;
}

来不及写注释了。麻烦各位巨佬!

2024/7/11 16:02
加载中...