P3369 【模板】普通平衡树 / P6136——FHQ treap

思路讲解

这个写的还是挺好的。

https://writings.sh/post/fhq-treap#合并-merge

AC代码

AC https://www.luogu.com.cn/record/219061889

源代码

// Problem: #104. 普通平衡树
// Contest: LibreOJ
// URL: https://loj.ac/p/104
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : \
variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
#define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin(), \
var.end())-var.begin());} while (0)
#define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } \ 
std::cerr<<"\n"; }while(0)
#define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto \
& pair : variable) \
{ std::cerr << "  " << pair.first << " => " << pair.second << "\n"; } \
std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT;
/*

*/
// namespace F=FHQ;		使用的时候简化可以这样
namespace FHQ{	// fhq-treap 使用namespace可以即起到打包，又避免实例化
	const int maxn=static_cast<ll>(1.1e6)+10;
	using KEY=int;
	KEY key[maxn];
	int pri[maxn],ls[maxn],rs[maxn],size[maxn];
	int root=0,cnt=0;
	// 超int范围问题不大，反正是正的负的也无所谓，他也不报错反正
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	inline void makeN(KEY val){++cnt;pri[cnt]=rng();key[cnt]=val;ls[cnt]=0;rs[cnt]=0;
	size[cnt]=1;}
	// pushup 相当于有清空和向上传递两层意义
	inline void pushup(int node){size[node]=size[ls[node]]+size[rs[node]]+1;}
	//把树 node 按值 val 分裂成两颗子树：左边的 x 和 右边的 y。
	void split(int node,KEY val,int &x,int &y){	
		if(!node) {x=0,y=0;return;}
		if(key[node]<=val){
			x=node;		// 左树，包括他自己，全部<=val（因为左树符合条件，不需要重新选一个了）
			split(rs[node],val,rs[node],y);		// 右树还要继续分
		}else{	// key[node]>val,说明右树（包括他自己）全部大于val
			y=node;	
			// x其实是从更上面传下来的rs[node]，其实是想找一个比<=val的右树
			split(ls[node],val,x,ls[node]);
		}
		pushup(node);
	}
	// 按pri合并，pri小的在上面
	int merge(int x,int y){
		if(!x || !y) return x+y;
		if(pri[x]<pri[y]){
			// 那么x是左树，左子树自然是不用动的
			rs[x]=merge(rs[x],y);	// 这个顺序其实是为了不会破坏BST性质，因为rs[x]<=y(key)
			pushup(x);
			return x;
		}else{
			// y是右树，右子树自然不用动
			ls[y]=merge(x,ls[y]);
			pushup(y);
			return y;
		}
	}
	inline void insert(KEY val){
		int x,y;	// 将树按值分裂为两个子树
		split(root,val,x,y);
		makeN(val);	// 新建节点cnt
		root=merge(x,cnt);
		root=merge(root,y);
	}
	inline void del(KEY val){
		int x,y,z;
		split(root,val,x,y);
		split(x,val-1,x,z);
		z=merge(ls[z],rs[z]);
		root=merge(x,z);
		root=merge(root,y);
	}
	inline int getrank(KEY val){
		int x,y;
		// 因为分裂出来一颗树<=val-1，另外一颗树<val
		split(root,val-1,x,y);
		int ret=size[x]+1;
		root=merge(x,y);
		return ret;
	}
	KEY _kth(int node,int rank){
		if(size[ls[node]]>=rank){
			return _kth(ls[node],rank);
		}else{
			if(size[ls[node]]+1>=rank) return key[node];
			else return _kth(rs[node],rank-size[ls[node]]-1);
		}
	}
	inline KEY kth(int rank){
		return _kth(root,rank);
	}
	inline KEY prex(KEY val){return kth(getrank(val)-1);}
	inline KEY sufx(KEY val){return kth(getrank(val+1));}
} 
inline void solve(){
	scanf("%lld",&N);
	int up=0;
	namespace F=FHQ;
	FOR(_,1,N){
		int op,x;
		scanf("%d%d",&op,&x);
		if(op==1){FHQ::insert(x);}
		else if(op==2){F::del(x);}
		else if(op==3){printf("%d\n",up=FHQ::getrank(x));}
		else if(op==4){printf("%d\n",up=FHQ::kth(x));}
		else if(op==5){printf("%d\n",up=FHQ::prex(x));}
		else if(op==6){printf("%d\n",up=FHQ::sufx(x));}
	}
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	// scanf("%lld",&lT);
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC https://loj.ac/s/2331639
AC https://www.luogu.com.cn/record/219061889
*/

和替罪羊树相比确实常数略大。

源代码

// Problem: P6136 【模板】普通平衡树（数据加强版）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6136
// Memory Limit: 89 MB
// Time Limit: 3000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
#define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin(),var.end())-var.begin());} while (0)
#define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } std::cerr<<"\n"; }while(0)
#define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto& pair : variable) { std::cerr << "  " << pair.first << " => " << pair.second << "\n"; } std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
// namespace F=FHQ;		使用的时候简化可以这样
namespace FHQ{	// fhq-treap 使用namespace可以即起到打包，又避免实例化
	const int maxn=static_cast<ll>(1.1e6)+10;
	using KEY=int;
	KEY key[maxn];
	int pri[maxn],ls[maxn],rs[maxn],size[maxn];
	int root=0,cnt=0;
	// 超int范围问题不大，反正是正的负的也无所谓，他也不报错反正
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	inline void makeN(KEY val){++cnt;pri[cnt]=rng();key[cnt]=val;ls[cnt]=0;rs[cnt]=0;
	size[cnt]=1;}
	// pushup 相当于有清空和向上传递两层意义
	inline void pushup(int node){size[node]=size[ls[node]]+size[rs[node]]+1;}
	//把树 node 按值 val 分裂成两颗子树：左边的 x 和 右边的 y。
	void split(int node,KEY val,int &x,int &y){	
		if(!node) {x=0,y=0;return;}
		if(key[node]<=val){
			x=node;		// 左树，包括他自己，全部<=val（因为左树符合条件，不需要重新选一个了）
			split(rs[node],val,rs[node],y);		// 右树还要继续分
		}else{	// key[node]>val,说明右树（包括他自己）全部大于val
			y=node;	
			// x其实是从更上面传下来的rs[node]，其实是想找一个比<=val的右树
			split(ls[node],val,x,ls[node]);
		}
		pushup(node);
	}
	// 按pri合并，pri小的在上面
	int merge(int x,int y){
		if(!x || !y) return x+y;
		if(pri[x]<pri[y]){
			// 那么x是左树，左子树自然是不用动的
			rs[x]=merge(rs[x],y);	// 这个顺序其实是为了不会破坏BST性质，因为rs[x]<=y(key)
			pushup(x);
			return x;
		}else{
			// y是右树，右子树自然不用动
			ls[y]=merge(x,ls[y]);
			pushup(y);
			return y;
		}
	}
	inline void insert(KEY val){
		int x,y;	// 将树按值分裂为两个子树
		split(root,val,x,y);
		makeN(val);	// 新建节点cnt
		root=merge(x,cnt);
		root=merge(root,y);
	}
	inline void del(KEY val){
		int x,y,z;
		split(root,val,x,y);
		split(x,val-1,x,z);
		z=merge(ls[z],rs[z]);
		root=merge(x,z);
		root=merge(root,y);
	}
	inline int getrank(KEY val){
		int x,y;
		// 因为分裂出来一颗树<=val-1，另外一颗树<val
		split(root,val-1,x,y);
		int ret=size[x]+1;
		root=merge(x,y);
		return ret;
	}
	KEY _kth(int node,int rank){
		if(size[ls[node]]>=rank){
			return _kth(ls[node],rank);
		}else{
			if(size[ls[node]]+1>=rank) return key[node];
			else return _kth(rs[node],rank-size[ls[node]]-1);
		}
	}
	inline KEY kth(int rank){
		return _kth(root,rank);
	}
	inline KEY prex(KEY val){return kth(getrank(val)-1);}
	inline KEY sufx(KEY val){return kth(getrank(val+1));}
} 

inline void solve(){
	scanf("%lld%lld",&N,&M);
	namespace F=FHQ;
	FOR(_,1,N){
		int x;
		scanf("%d",&x);F::insert(x);
	}
	int up=0,ans=0;
	FOR(_,1,M){
		int op,x;
		scanf("%d%d",&op,&x);
		x^=up;
		if(op==1){F::insert(x);}
		else if(op==2){F::del(x);}
		else if(op==3){up=FHQ::getrank(x);ans^=up;}
		else if(op==4){up=F::kth(x);ans^=up;}
		else if(op==5){up=F::prex(x);ans^=up;}
		else if(op==6){up=F::sufx(x);ans^=up;}
	}
	printf("%d\n",ans);
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	// scanf("%lld",&lT);
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC https://www.luogu.com.cn/record/219062740
*/

心路历程（WA，TLE，MLE……）