P6136 【模板】普通平衡树（数据加强版） · znzryb
## 思路讲解
FHQ-Treap
[https://www.luogu.com.cn/article/vj041eul](https://www.luogu.com.cn/article/vj041eul)
## AC代码
AC
[https://www.luogu.com.cn/record/200519720](https://www.luogu.com.cn/record/200519720)
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
const ll MAXN = static_cast<ll>(4e6) + 10;
ll N, M, idx, root, last, ans;
mt19937 rng(time(0));
// 值 随机值
ll son[MAXN][2], size[MAXN], key[MAXN], rad[MAXN];
inline void resize(ll k) { size[k] = size[son[k][0]] + size[son[k][1]] + 1; }
// split函数返回的是分裂出来的左子树和右子树的编号
// 根与按值分裂的值
pll split(ll u, ll k) {
// 这里按值分裂,分裂为左子树<k，右子树>=k;
if (!u)
return {0, 0}; // 递归终止条件
if (key[u] < k) {
// 继续分裂右子树（左子树全部<k，也都符合条件）
pll t = split(son[u][1], k);
son[u][1] = t.first;
resize(u); // 重新计算树大小
// 进入到了这个节点，就是来找左子树中有没有>=k的值的
return {u, t.second};
} else {
// 继续分裂左子树（右子树全部>=k，都符合条件）
pll t = split(son[u][0], k);
son[u][0] = t.second;
resize(u);
// 进入到了这个节点，就是来找右子树中有没有<k的值的，右子树中<k的值的就是在左子树
return {t.first, u};
}
}
// merge函数接受两个参数，为两棵树的根；返回合并后的根。
ll merge(ll u, ll v) {
if (!u | !v)
return u + v; // 如果任何一棵树为空，返回另一棵树
if (rad[u] < rad[v]) {
// 小根堆，我们让随机值小的u当根，merge左子树
son[u][1] = merge(son[u][1], v);
resize(u);
return u;
} else {
// u值比较大，当v的右边
son[v][0] = merge(u, son[v][0]);
resize(v);
return v;
}
}
inline void insert(ll k) {
key[++idx] = k;
rad[idx] = rng();
size[idx] = 1;
pll t = split(root, k);
root = merge(merge(t.first, idx), t.second);
}
inline void eraser(ll k) {
pll x = split(root, k);
// x.second 是所有>=k的，所以y就分成了=k的和>k的
pll y = split(x.second, k + 1);
// 把=k的根节点吃掉了
y.first = merge(son[y.first][0], son[y.first][1]);
// 依次合并起来，更新根
root = merge(x.first, merge(y.first, y.second));
}
// 查询k的排名
inline ll find1(ll k) {
pll t = split(root, k);
ll rank = size[t.first] + 1;
root = merge(t.first, t.second);
return rank;
}
// 根据排名找数
inline ll find2(ll rank) {
ll pos = root;
while (pos) {
if (rank == size[son[pos][0]] + 1)
return key[pos];
else if (size[son[pos][0]] + 1 > rank)
pos = son[pos][0];
else
rank -= size[son[pos][0]] + 1, pos = son[pos][1];
}
return 0;
}
// 查询前驱
inline ll lst(ll k) { return find2(find1(k) - 1); }
// 直接find1(k+1)，查询的值+1，避免了值相同的问题
inline ll nxt(ll k) { return find2(find1(k + 1)); }
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; ++i) {
ll a;
cin >> a;
insert(a);
}
// cout<<"debug "<<0<<" :\n";
// cout<<root<<'\n';
// for(int j=1;j<=N;++j) {
// cout<<"son "<<key[j]<<" "<<key[son[j][0]]<<' '<<key[son[j][1]]<<'\n';
// }
for(int i=1;i<=M;i++){
ll o,x;
cin>>o>>x;
// x^=last;
if(o==1) insert(x^last);
if(o==2) eraser(x^last);
if(o==3) { last=find1(x^last); ans^=last; }
if(o==4) { last=find2(x^last); ans^=last; }
if(o==5) { last=lst(x^last); ans^=last; }
if(o==6) { last=nxt(x^last); ans^=last; }
// cout<<"debug "<<i<<" :\n";
// for(int j=1;j<=N;++j) {
// cout<<"son "<<key[j]<<" "<<key[son[j][0]]<<' '<<key[son[j][1]]<<'\n';
// }
}
cout<<ans<<endl;
return 0;
}
/*
AC https://www.luogu.com.cn/record/200519720
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 8
3 13
6 7
1 4
*/
```
## 心路历程（WA，TLE，MLE……）
各种奇怪的地方吧，导致WA了。