P6136 【模板】普通平衡树（数据加强版）——替罪羊树 · znzryb
## 思路讲解
[P3369 【模板】普通平衡树——替罪羊树](/2025/05/27/20250527-bbf82dc3)
## AC代码
[https://www.luogu.com.cn/record/218794056](https://www.luogu.com.cn/record/218794056)
::: 源代码
```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];
/*
*/
// ScapeoGoat Tree 替罪羊英文太难写了
// 代码具有一定的鲁棒性，不要求del操作，prex，sufx操作合法。
// getrank操作不要求x曾经出现过
class ScapeGoatTree{
// 根据题目选择合适的maxn
private:
typedef int KEY; // 如果key的值比较大，可以改为ll
static const int maxn=static_cast<int>(1.1e6)+7,inf=static_cast<KEY>(2e9)+7;
static constexpr DB alpha=0.7;
// diff为节点总数（用于调整），size为数字总数（用于询问）
int ls[maxn],rs[maxn],count[maxn],diff[maxn],size[maxn];
bool isdel[maxn];
KEY key[maxn]; // 其他都不太可能是ll，但是key可能是，所以单列
int collect[maxn],ci=0; // 中序遍历收集数组以及收集了几个
// 最上方不平衡节点（top），其父节点（father），其为父节点的什么孩子（side）（1-left，2r）
int top=0,father=0;bool side=false;
// 0是一个超级源点，那么1是一个辅助节点，其节点里没有值（即key=0）
int head=1,cnt=1; // 这是因为我们要访问father，因为我们从不进入0，改为什么值不影响
bool neebal=false;
inline void makeN(int node,KEY val){
ls[node]=0,rs[node]=0,count[node]=1,diff[node]=1,size[node]=1;
key[node]=val;
}
inline void initN(int node){
if(node!=1 && node!=0) ls[node]=0,rs[node]=0,size[node]=count[node],diff[node]=1;
else ls[node]=0,rs[node]=0,size[node]=count[node],diff[node]=0;
}
inline bool isbal(int node){
// （dummy）哑元节点不应该参与这种平衡判断，那我们默认一定是平衡的
if(node==1 || node==0) return true;
int mxDiff=max(diff[ls[node]],diff[rs[node]]);
// 最大的子树超过总树的0.7被认为是不平衡的
if(mxDiff>diff[node]*alpha) return false;
return true;
}
// bool值用来确定是否创建了一个新的点
bool insert(int node,KEY val,int fa,bool isLeft){
// #ifdef LOCAL
// debug(node);
// debug(key[node]);
// debug(val);
// #endif
if(key[node]==val){
++count[node];
++size[node];
isdel[node]=false; // 删除节点后，又加入了该节点，需要修改节点状态重新为isdel=false
return false;
}else if(val>key[node]){
++size[node];
if(rs[node]==0){
rs[node]=++cnt;
makeN(cnt,val);
return true;
}else{
bool ret=insert(rs[node],val,node,false);
if(ret){ // 只有的确新增节点的时候，才需要重新计算平衡值
++diff[node];
// 不平衡，需要平衡操作
if(!isbal(node)) top=node,father=fa,side=isLeft,neebal=true;
return ret;
}else{
return ret;
}
}
}else{
++size[node];
if(ls[node]==0){
ls[node]=++cnt;
makeN(cnt,val);
return true;
}else{
bool ret=insert(ls[node],val,node,true);
if(ret){
++diff[node];
if(!isbal(node)) top=node,father=fa,side=isLeft,neebal=true;
return ret;
}else{
return ret;
}
}
}
}
void inorder(int node){
if(ls[node]!=0){inorder(ls[node]);}
if(!isdel[node]) collect[++ci]=node;
if(rs[node]!=0){inorder(rs[node]);}
}
void rebuild(int l,int r){
// #ifdef LOCAL
// debug(l);
// debug(r);
// cerr<<"\n";
// #endif
int mid=l+r>>1;
int node=collect[mid];
initN(node);
if(l>=r) return;
if(l<=mid-1){
rebuild(l,mid-1);
int node1=collect[(l+mid-1)>>1];
ls[node]=node1,size[node]+=size[node1],diff[node]+=diff[node1];
}
if(r>=mid+1){
rebuild(mid+1,r);
int node2=collect[(r+mid+1)>>1];
rs[node]=node2,size[node]+=size[node2],diff[node]+=diff[node2];
}
}
inline void balan(){
ci=0;
inorder(top);
if(ci>0){
int lhead=collect[(1+ci)/2];
if(top==head) head=lhead; // 说明要从头节点开始重构
if(side) {ls[father]=lhead;}
else {rs[father]=lhead;}
rebuild(1,ci);
}
ci=0,top=0,neebal=false,father=0,side=false; // 复位。
}
// 返回是不是真正删除了改节点，返回1代表有这个val节点，但节点count>1，返回2代表彻底删除，
// 返回0代表没有该节点。
int del(int node,KEY val/*,int fa,bool isLeft*/){
if(key[node]==val){
if(count[node]>1){
--count[node];
--size[node];
return 1;
}else{
count[node]=0;
--diff[node];
--size[node];
isdel[node]=true;
return 2;
}
}else if(val>key[node]){
int ret=0;
if(rs[node]!=0) ret=del(rs[node],val/*,node,false*/);
if(ret!=0) --size[node];
if(ret==2) {
--diff[node];
// if(!isbal(node)) top=node,father=fa,side=isLeft,neebal=true;
}
return ret;
}else{
int ret=0;
if(ls[node]!=0) ret=del(ls[node],val/*,node,false*/);
if(ret!=0) --size[node];
if(ret==2) {
--diff[node];
// if(!isbal(node)) top=node,father=fa,side=isLeft,neebal=true;
}
return ret;
}
}
int getrank(int node,KEY val,int k){ // 不需要涉及重构，不用传入那么多参数
if(key[node]==val){ // 多少数比val小，并且讲得到的答案+1
k+=size[ls[node]];
k+=1;
return k;
}else if(val>key[node]){
k+=size[ls[node]];
k+=count[node];
if(rs[node]!=0){
return getrank(rs[node],val,k);
}else{
return k+1;
}
}else{
if(ls[node]!=0){
return getrank(ls[node],val,k);
}else{
return k+1;
}
}
}
KEY kth(int node,int k){
// #ifdef LOCAL
// debug(node);
// debug(k);
// #endif
if(size[ls[node]]>=k){
if(ls[node]!=0){
return kth(ls[node],k);
}else{
return -inf;
}
}else{
// #ifdef LOCAL
// debug((size[ls[node]]+count[node]>=k));
// debug((rs[node]==0));
// debug(size[ls[node]]);
// debug(count[node]);
// cerr<<"\n";
// #endif
if(size[ls[node]]+count[node]>=k){
return key[node];
}else{
if(rs[node]!=0){
return kth(rs[node],k-(size[ls[node]]+count[node]));
}else{
return -inf;
}
}
}
}
KEY ans=-inf;
void prex(int node,KEY val){
if(key[node]>=val){
if(ls[node]!=0) prex(ls[node],val);
}else{
if(!isdel[node]){ // 如果该节点没有删除，那看一看更大的，因为更小的不可能比这个优越
ans=max(ans,key[node]);
if(rs[node]!=0) prex(rs[node],val);
}else{
if(ls[node]!=0) prex(ls[node],val);
if(rs[node]!=0) prex(rs[node],val);
}
}
}
void sufx(int node,KEY val){
#ifdef LOCAL
if(val==129173){
debug(node);
debug(key[node]);
debug(isdel[node])
// debug(val);
}
#endif
if(key[node]<=val){
if(rs[node]!=0) sufx(rs[node],val);
}else{
if(!isdel[node]){ // 如果该节点没有删除，那看一看更小的，因为更大的不可能比这个优越
ans=min(ans,key[node]);
if(ls[node]!=0) sufx(ls[node],val);
}else{
if(ls[node]!=0) sufx(ls[node],val);
if(rs[node]!=0) sufx(rs[node],val);
}
}
}
public: // 开放的接口（api）
inline void insert(KEY val){ // 这个insert参数和那个不同，是对外的
insert(head,val,0,false); // 0作为fa传入只是为了防止fa指向自己造成的一系列问题
if(neebal){
balan();
}
}
inline void del(KEY val){
del(head,val/*,0,false*/);
// if(neebal){
// balan();
// }
}
inline int getrank(KEY val){
return getrank(head,val,0);
}
inline KEY kth(int k){
return kth(head,k);
}
inline KEY prex(KEY val){ // 前驱定义为小于 x，且最大的数
ans=-inf;
prex(head,val);
return ans;
}
inline KEY sufx(KEY val){ // 后继定义为大于 x，且最小的数
ans=inf;
sufx(head,val);
return ans;
}
ScapeGoatTree() { // 构造函数
// 由于可能有0，所以我们设置key[1]=-inf这个无法到达的值。
key[1] = -inf;
// 这个是因为如果发生异常，就会输出节点0的值，这个时候抛出-inf就非常明显
key[0] = -inf;
}
inline void clear() {
memset(key, 0, sizeof(key));
memset(count, 0, sizeof(count));memset(isdel,0,sizeof(isdel));
memset(ls, 0, sizeof(ls));memset(rs, 0, sizeof(rs));
memset(size, 0, sizeof(size));memset(diff, 0, sizeof(diff));
memset(collect,0,sizeof(collect));ci=0;cnt = 1;head = 1;
key[1] = -inf;key[0] = -inf;
}
};
ScapeGoatTree tr=ScapeGoatTree();
inline void solve(){
scanf("%lld%lld",&N,&M);
FOR(_,1,N){
int x;
scanf("%d",&x);tr.insert(x);
}
int up=0,ans=0;
FOR(_,1,M){
int op,x;
scanf("%d%d",&op,&x);
x^=up;
if(op==1){tr.insert(x);}
else if(op==2){tr.del(x);}
else if(op==3){up=tr.getrank(x);ans^=up;}
else if(op==4){up=tr.kth(x);ans^=up;}
else if(op==5){up=tr.prex(x);ans^=up;}
else if(op==6){up=tr.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/218794056
*/
```
:::
简化版，prex和sufx复用了kth，和getrank
::: 源代码
```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];
/*
*/
// ScapeoGoat Tree 替罪羊英文太难写了
// 代码具有一定的鲁棒性，不要求del操作，prex，sufx操作合法。
// getrank操作不要求x曾经出现过
class ScapeGoatTree{
// 根据题目选择合适的maxn
private:
typedef int KEY; // 如果key的值比较大，可以改为ll
// 空间大概是占大约30MB，maxn=1.1e6+7
static const int maxn=static_cast<int>(1.1e6)+7,inf=static_cast<KEY>(2e9)+7;
static constexpr DB alpha=0.7;
// diff为节点总数（用于调整），size为数字总数（用于询问）
int ls[maxn],rs[maxn],count[maxn],diff[maxn],size[maxn];
bool isdel[maxn];
KEY key[maxn]; // 其他都不太可能是ll，但是key可能是，所以单列
int collect[maxn],ci=0; // 中序遍历收集数组以及收集了几个
// 最上方不平衡节点（top），其父节点（father），其为父节点的什么孩子（side）（1-left，2r）
int top=0,father=0;bool side=false;
// 0是一个超级源点，那么1是一个辅助节点，其节点里没有值（即key=0）
int head=1,cnt=1; // 这是因为我们要访问father，因为我们从不进入0，改为什么值不影响
bool neebal=false;
inline void makeN(int node,KEY val){
ls[node]=0,rs[node]=0,count[node]=1,diff[node]=1,size[node]=1;
key[node]=val;
}
inline void initN(int node){
if(node!=1 && node!=0) ls[node]=0,rs[node]=0,size[node]=count[node],diff[node]=1;
else ls[node]=0,rs[node]=0,size[node]=count[node],diff[node]=0;
}
inline bool isbal(int node){
// （dummy）哑元节点不应该参与这种平衡判断，那我们默认一定是平衡的
if(node==1 || node==0) return true;
int mxDiff=max(diff[ls[node]],diff[rs[node]]);
// 最大的子树超过总树的0.7被认为是不平衡的
if(mxDiff>diff[node]*alpha) return false;
return true;
}
// bool值用来确定是否创建了一个新的点
bool insert(int node,KEY val,int fa,bool isLeft){
if(key[node]==val){
++count[node];
++size[node];
isdel[node]=false; // 删除节点后，又加入了该节点，需要修改节点状态重新为isdel=false
return false;
}else if(val>key[node]){
++size[node];
if(rs[node]==0){
rs[node]=++cnt;
makeN(cnt,val);
return true;
}else{
bool ret=insert(rs[node],val,node,false);
if(ret){ // 只有的确新增节点的时候，才需要重新计算平衡值
++diff[node];
// 不平衡，需要平衡操作
if(!isbal(node)) top=node,father=fa,side=isLeft,neebal=true;
return ret;
}else{
return ret;
}
}
}else{
++size[node];
if(ls[node]==0){
ls[node]=++cnt;
makeN(cnt,val);
return true;
}else{
bool ret=insert(ls[node],val,node,true);
if(ret){
++diff[node];
if(!isbal(node)) top=node,father=fa,side=isLeft,neebal=true;
return ret;
}else{
return ret;
}
}
}
}
void inorder(int node){
if(ls[node]!=0){inorder(ls[node]);}
if(!isdel[node]) collect[++ci]=node;
if(rs[node]!=0){inorder(rs[node]);}
}
void rebuild(int l,int r){
int mid=l+r>>1;
int node=collect[mid];
initN(node);
if(l>=r) return;
if(l<=mid-1){
rebuild(l,mid-1);
int node1=collect[(l+mid-1)>>1];
ls[node]=node1,size[node]+=size[node1],diff[node]+=diff[node1];
}
if(r>=mid+1){
rebuild(mid+1,r);
int node2=collect[(r+mid+1)>>1];
rs[node]=node2,size[node]+=size[node2],diff[node]+=diff[node2];
}
}
inline void balan(){
ci=0;
inorder(top);
if(ci>0){
int lhead=collect[(1+ci)/2];
if(top==head) head=lhead; // 说明要从头节点开始重构
if(side) {ls[father]=lhead;}
else {rs[father]=lhead;}
rebuild(1,ci);
}
ci=0,top=0,neebal=false,father=0,side=false; // 复位。
}
// 返回是不是真正删除了改节点，返回1代表有这个val节点，但节点count>1，返回2代表彻底删除，
// 返回0代表没有该节点。
int del(int node,KEY val/*,int fa,bool isLeft*/){
if(key[node]==val){
if(count[node]>1){
--count[node];
--size[node];
return 1;
}else{
count[node]=0;
--diff[node];
--size[node];
isdel[node]=true;
return 2;
}
}else if(val>key[node]){
int ret=0;
if(rs[node]!=0) ret=del(rs[node],val/*,node,false*/);
if(ret!=0) --size[node];
if(ret==2) {
--diff[node];
}
return ret;
}else{
int ret=0;
if(ls[node]!=0) ret=del(ls[node],val/*,node,false*/);
if(ret!=0) --size[node];
if(ret==2) {
--diff[node];
}
return ret;
}
}
int getrank(int node,KEY val,int k){ // 不需要涉及重构，不用传入那么多参数
if(key[node]==val){ // 多少数比val小，并且讲得到的答案+1
k+=size[ls[node]];
k+=1;
return k;
}else if(val>key[node]){
k+=size[ls[node]];
k+=count[node];
if(rs[node]!=0){
return getrank(rs[node],val,k);
}else{
return k+1;
}
}else{
if(ls[node]!=0){
return getrank(ls[node],val,k);
}else{
return k+1;
}
}
}
KEY kth(int node,int k){
if(size[ls[node]]>=k){
if(ls[node]!=0){
return kth(ls[node],k);
}else{
return -inf;
}
}else{
if(size[ls[node]]+count[node]>=k){
return key[node];
}else{
if(rs[node]!=0){
return kth(rs[node],k-(size[ls[node]]+count[node]));
}else{
return -inf;
}
}
}
}
public: // 开放的接口（api）
inline void insert(KEY val){ // 这个insert参数和那个不同，是对外的
insert(head,val,0,false); // 0作为fa传入只是为了防止fa指向自己造成的一系列问题
if(neebal){
balan();
}
}
inline void del(KEY val){
del(head,val/*,0,false*/);
// if(neebal){
// balan();
// }
}
inline int getrank(KEY val){
return getrank(head,val,0);
}
inline KEY kth(int k){
return kth(head,k);
}
inline KEY prex(KEY val){ // 前驱定义为小于 x，且最大的数
return kth(getrank(val)-1); // 这个其实意思是
}
inline KEY sufx(KEY val){ // 后继定义为大于 x，且最小的数
return kth(getrank(val+1));
}
ScapeGoatTree() { // 构造函数
// 由于可能有0，所以我们设置key[1]=-inf这个无法到达的值。
key[1] = -inf;
// 这个是因为如果发生异常，就会输出节点0的值，这个时候抛出-inf就非常明显
key[0] = -inf;
}
inline void clear() {
memset(key, 0, sizeof(key));
memset(count, 0, sizeof(count));memset(isdel,0,sizeof(isdel));
memset(ls, 0, sizeof(ls));memset(rs, 0, sizeof(rs));
memset(size, 0, sizeof(size));memset(diff, 0, sizeof(diff));
memset(collect,0,sizeof(collect));ci=0;cnt = 1;head = 1;
key[1] = -inf;key[0] = -inf;
}
};
ScapeGoatTree tr=ScapeGoatTree();
inline void solve(){
scanf("%lld%lld",&N,&M);
FOR(_,1,N){
int x;
scanf("%d",&x);tr.insert(x);
}
int up=0,ans=0;
FOR(_,1,M){
int op,x;
scanf("%d%d",&op,&x);
x^=up;
if(op==1){tr.insert(x);}
else if(op==2){tr.del(x);}
else if(op==3){up=tr.getrank(x);ans^=up;}
else if(op==4){up=tr.kth(x);ans^=up;}
else if(op==5){up=tr.prex(x);ans^=up;}
else if(op==6){up=tr.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/218794056
简化版
AC https://www.luogu.com.cn/record/218798712
*/
```
:::
## 心路历程（WA，TLE，MLE……）