P3369 【模板】普通平衡树 / P6136——FHQ treap · znzryb
## 思路讲解
这个写的还是挺好的。
[https://writings.sh/post/fhq-treap#合并-merge](https://writings.sh/post/fhq-treap#%E5%90%88%E5%B9%B6-merge)
## AC代码
AC [https://www.luogu.com.cn/record/219061889](https://www.luogu.com.cn/record/219061889)
::: 源代码
```cpp
// 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
*/
```
:::
和替罪羊树相比确实常数略大。
::: 源代码
```cpp
// 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……）