萌新刚学一秒fhq-Treap求调
查看原帖
萌新刚学一秒fhq-Treap求调
198964
Msents楼主2023/1/31 09:53

关于count的计算有问题,不知道怎么改

#include<bits/stdc++.h>
using namespace std;
int n;
struct Node{
	int key;
	int val;
	int count;
	int lc,rc;
}tree[800000+1];
int sign=0;
int root=0;
mt19937 rander(100000);
void PushUp(int k){
	tree[k].count=1;
	if(tree[k].lc)tree[k].count+=tree[tree[k].lc].count;
	if(tree[k].rc)tree[k].count+=tree[tree[k].rc].count;
}
pair<int,int>Split(int k,int val){//按val切割以k为根的树,返回两棵树
//cout<<'s'<<'\n';
	if(!k)return make_pair(0,0);
	else if(tree[k].val<=val){
		pair<int,int>p=Split(tree[k].rc,val);
		tree[k].rc=p.first;
		PushUp(k);
		return make_pair(k,p.second);
	}else{
		pair<int,int>p=Split(tree[k].lc,val);
		tree[k].lc=p.second;
		PushUp(k);
		return make_pair(p.first,k);
	}
}
int Merge(int k1,int k2){
//cout<<'m'<<'\n';
	if((!k1)||(!k2))return k1+k2;
	else if(tree[k1].key<tree[k2].key){
		tree[k1].rc=Merge(tree[k1].rc,k2);
		PushUp(k1);
		return k1;
	}else{
		tree[k2].lc=Merge(k1,tree[k2].lc);
		PushUp(k2);
		return k2;
	}
}
void Insert(int val){
	if(!root){
		root=++sign;
		tree[root].count=1;
		tree[root].val=val;
		tree[root].key=rander();
		return;
	}
	pair<int,int>p=Split(root,val);
	++sign;
	tree[root].count=1;
	tree[sign].val=val;
	tree[sign].key=rander();
	root=Merge(p.first,Merge(sign,p.second));
}
void Delete(int val){
	pair<int,int>p1=Split(root,val);
	pair<int,int>p2=Split(p1.first,val-1);
	int newR=Merge(tree[p2.second].lc,tree[p2.second].rc);
	root=Merge(Merge(p2.first,newR),p1.second);
}
int Rank(int val){
	pair<int,int>p=Split(root,val-1);
	int ret=tree[p.first].count+1;
	root=Merge(p.first,p.second);
	return ret;
}
int At(int rank){
	int now=root;
	while(true){
		if(rank<=tree[tree[now].lc].count)now=tree[now].lc;
		else if(rank==tree[tree[now].lc].count+1){
			return tree[now].val;
		}else{
			rank-=tree[tree[now].lc].count+1;
			now=tree[now].rc;
		}
	}
}
int Pre(int x){
	pair<int,int>p=Split(root,x-1);
	int ans,now=p.first;
	while(true){
//cerr<<tree[now].val<<'p';
		if(tree[now].rc)now=tree[now].rc;
		else{
			ans=tree[now].val;
			break;
		}
	}
//cerr<<endl;
	root=Merge(p.first,p.second);
	return ans;
}
int Suc(int x){
	pair<int,int>p=Split(root,x);
	int ans,now=p.second;
	while(true){
		if(tree[now].lc)now=tree[now].lc;
		else{
			ans=tree[now].val;
			break;
		}
	}
	root=Merge(p.first,p.second);
	return ans;
}
void Solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int op,x;
		cin>>op>>x;
		if(op==1){
			Insert(x);
		}else if(op==2){
			Delete(x);
		}else if(op==3){
			cout<<Rank(x)<<'\n';
		}else if(op==4){
			cout<<At(x)<<'\n';
		}else if(op==5){
			cout<<Pre(x)<<'\n';
		}else if(op==6){
			cout<<Suc(x)<<'\n';
		}
for(int i=1;i<=8;i++)cout<<'-';
cout<<'\n';
cout<<root;
cout<<'\n';
for(int i=1;i<=sign;i++)
	cout<<tree[i].val<<' '
		<<tree[i].key<<' '
		<<tree[i].count<<' '
		<<tree[i].lc<<' '
		<<tree[i].rc<<'\n';
for(int i=1;i<=8;i++)cout<<'-';
cout<<endl;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	Solve();
	return 0;
}
2023/1/31 09:53
加载中...