P6136 【模板】普通平衡树（数据加强版）——替罪羊树

思路讲解

P3369 【模板】普通平衡树——替罪羊树

AC代码

https://www.luogu.com.cn/record/218794056

源代码

// 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

源代码

// 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……）