Znzryb's Blog

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

Posted on 2025-05-27 Edited on 2026-02-17

思路讲解

【算法讲解150【扩展】有序表专题3-替罪羊树】 https://www.bilibili.com/video/BV1GqDSYbEPR/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

总体上来说替罪羊树的思想还是比较简单的，但是其实真写起来还是会有挺多要注意的地方的。

prex，sufx如何改用kth和getrank实现？说白了，其实我们能保证 $kth(getrank(val))≥val$ ，那我们自然也可以保证 $kth(getrank(val)-1)<val$ 。

inline KEY prex(KEY val){ 	// 前驱定义为小于 x，且最大的数
	return kth(getrank(val)-1);	
}
inline KEY sufx(KEY val){	// 后继定义为大于 x，且最小的数
	return kth(getrank(val+1));		// 所有<=25的数就是<26的数的个数
	// kth(getrank(val)+1);	-> 89851 而非 84185，是因为kth(getrank(val))本身就可能>val
}

AC代码

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

源代码

// Problem: P3369 【模板】普通平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3369
// Memory Limit: 128 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 __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
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;
/*

*/

// ScapeoGoat Tree 替罪羊英文太难写了
// 代码具有一定的鲁棒性，不要求del操作，prex，sufx操作合法。
// getrank操作不要求x曾经出现过
class ScapeGoatTree{
	// 根据题目选择合适的maxn
private:
	typedef int KEY;	// 如果key的值比较大，可以改为ll
	static const int maxn=static_cast<int>(1e5)+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",&N);
	int cnt=0,up;
	FOR(_,1,N){
		int op,x;
		scanf("%d%d",&op,&x);
		if(op==1){tr.insert(x);}
		else if(op==2){tr.del(x);}
		else if(op==3){printf("%d\n",up=tr.getrank(x));}
		else if(op==4){printf("%d\n",up=tr.kth(x));}
		else if(op==5){printf("%d\n",up=tr.prex(x));}
		else if(op==6){printf("%d\n",up=tr.sufx(x));}
		
		if(op!=1 && op!=2) ++cnt;
		if(cnt==2867){
#ifdef LOCAL
    debug(up);
    debug(op);
    debug(x);
    debug(_);
#endif
		}
	}
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC https://www.luogu.com.cn/record/218793914
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

106465
84185
492737
*/

源代码简化版

// Problem: P3369 【模板】普通平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3369
// Memory Limit: 128 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 __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
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;
/*

*/

// 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",&N);
	int cnt=0,up;
	FOR(_,1,N){
		int op,x;
		scanf("%d%d",&op,&x);
		if(op==1){tr.insert(x);}
		else if(op==2){tr.del(x);}
		else if(op==3){printf("%d\n",up=tr.getrank(x));}
		else if(op==4){printf("%d\n",up=tr.kth(x));}
		else if(op==5){printf("%d\n",up=tr.prex(x));}
		else if(op==6){printf("%d\n",up=tr.sufx(x));}
		
		if(op!=1 && op!=2) ++cnt;
		if(cnt==2867){
#ifdef LOCAL
    debug(up);
    debug(op);
    debug(x);
    debug(_);
#endif
		}
	}
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC https://www.luogu.com.cn/record/218793914
简化版，删掉了prex和sufx的实现
AC https://www.luogu.com.cn/record/218798476
*/

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

解决RE，MLE是靠把删除造成重构的代码给删了（觉得没必要）

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

源代码

// Problem: P3369 【模板】普通平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3369
// Memory Limit: 128 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.front())
#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 __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
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;
/*

*/

// ScapeoGoat Tree 替罪羊英文太难写了
// 代码具有一定的鲁棒性，不要求del操作，prex，sufx操作合法。
// getrank操作不要求x曾经出现过
class ScapeGoatTree{
	// 根据题目选择合适的maxn
private:
	typedef int KEY;	// 如果key的值比较大，可以改为ll
	static const int maxn=static_cast<int>(1e5)+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];
			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(){
		inorder(top);
		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{
			ans=max(ans,key[node]);
			if(rs[node]!=0) prex(rs[node],val);
			return;
		}
	}
	void sufx(int node,KEY val){
// #ifdef LOCAL
   	// debug(node);
   	// debug(val);
// #endif
		if(key[node]<=val){
			if(rs[node]!=0) sufx(rs[node],val);
		}else{
			ans=min(ans,key[node]);
			if(ls[node]!=0) sufx(ls[node],val);
		}
	}
public:		// 开放的接口（api）
	inline void insert(KEY val){	// 这个insert参数和那个不同，是对外的
		insert(head,val,0,false);	// 0作为fa传入只是为了防止fa指向自己造成的一系列问题
		if(neebal){
			balan();
#ifdef LOCAL
    cerr << "-------------" << '\n';
#endif
		}
	}
	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",&N);
	FOR(_,1,N){
		int op,x;
		scanf("%d%d",&op,&x);
		if(op==1){tr.insert(x);}
		else if(op==2){tr.del(x);}
		else if(op==3){printf("%d\n",tr.getrank(x));}
		else if(op==4){printf("%d\n",tr.kth(x));}
		else if(op==5){printf("%d\n",tr.prex(x));}
		else if(op==6){printf("%d\n",tr.sufx(x));}
	}
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

106465
84185
492737
*/

初步查明，是前驱后继未判断节点是否完全删除。

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);
		return;
	}
}

当然，上面这个代码也有点问题，删除后的节点，由于没更新的缘故，需要考虑更多情况

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);
		}
	}
}

WA2

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

初步查明，原因是删除节点后，又加入了该节点，需要修改节点状态重新为isdel=false

CF840D Destiny

Posted on 2025-05-27 Edited on 2026-02-17

思路讲解

那我们还是要确认一下，我们的这个模版啊，问题不是很大，所以我们来用cf的题目测一下。

就改了一下这个query部分，其他都没动。

// u v 为node，l，r为区间，k为区间第k小（实际上来说，表示区间的是u，v。l，r为值域）
int query(int u,int v,int l,int r,int k){
	if(l==r){
		if(sum[v]-sum[u]>=k) return l;
		else return INF;
	}
	// 我们这样就知道了
	int lsum=sum[ls[v]]-sum[ls[u]];
	int mid=l+r>>1;
	int ans1=INF,ans2=INF;
	if(lsum>=k){
		ans1=query(ls[u],ls[v],l,mid,k);
	}
	if(ans1==INF && sum[rs[v]]-sum[rs[u]]>=k){
		ans2=query(rs[u],rs[v],mid+1,r,k);
	}
	// ans1= ans1==0?INF:ans1;ans2= ans2==0?INF:ans2;
	return min(ans1,ans2);
}

AC代码

https://codeforces.com/contest/840/submission/321605622

源代码

// Problem: D. Destiny
// Contest: Codeforces - Codeforces Round 429 (Div. 1)
// URL: https://codeforces.com/problemset/problem/840/D
// Memory Limit: 512 MB
// Time Limit: 2500 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.front())
#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 __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10;
constexpr int INF=static_cast<int>(1e9)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

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

*/
struct persisTree{	// 单点修改区间查询的主席树，处理静态区间第 k 小问题。
	// 由于太大了，该结构体只能声明与全局变量作用域
	// 测试 https://www.luogu.com.cn/record/218615977 （只测了单次数据）
	// maxn为点的数量，maxm为版本数量（在静态区间第 k 小问题中，和maxn一样）
	static const int maxn=static_cast<int>(5e5)+7,maxm=static_cast<int>(5e5)+7;
	static const int LOGmxm=20;		// 这个版本次数一般也不会超过2**20，也就是1048576
	static const int maxn4=maxn*4+LOGmxm*maxn;
	int ls[maxn4],rs[maxn4],L[maxn4],R[maxn4],root[maxm];
	int arr[maxn],sum[maxn4],li[maxn];
	int n=0,m=0,idx=1,Cver=0,len=0;
	// root为不同版本的根。L，R为左端点 右端点，ls rs 为左孩子 右孩子，arr为原数组。
	inline int initLi(int ln,int lm){	// 离散化操作
		idx=1,n=ln,m=lm,Cver=0;
		root[0]=1;	// 版本0的根是1
		for(int i=1;i<=n;++i){
			li[i]=arr[i];
		}
		sort(li+1,li+1+n);
		len=unique(li+1,li+1+n)-li-1;	// 这个len是超了一个的
		return len;
	}
	inline int kth(ll x){
		int ret=lower_bound(li+1,li+1+len,x)-li;
		return ret;
	}
	inline void clone(int node){
		++idx;
		L[idx]=L[node];
		R[idx]=R[node];
		sum[idx]=sum[node];
		ls[idx]=ls[node];
		rs[idx]=rs[node];
	}
	void build(int node,int l,int r){
		ls[node]=++idx;
		rs[node]=++idx;
		L[node]=l;
		R[node]=r;
		sum[node]=0;
		if(l==r) return;
		build(ls[node],l,((l+r)>>1));
		build(rs[node],(l+r>>1)+1,r);
	}
	// 处理静态区间第 k 小问题中，因为权值线段树，x=1
	// 注意，node调用时应该填入想要加的版本的根，即tr.root[versionNeddModify]
	void add(int node,int ver,int p,ll x){ 	
		clone(node);
		sum[idx]+=x;
		if(p==L[node] && p==R[node]){
			return;
		}
		// 如果当前遍历到的点是一个版本的根，那么现在的点idx就是目前这个版本的根
		if(root[ver]==node){	
			++Cver;
			root[Cver]=idx;
		}
		if(p>=L[ls[node]] && p<=R[ls[node]]){
			int nals=ls[idx];
			ls[idx]=idx+1;
			add(nals,ver,p,x);
		}else{
			int nars=rs[idx];
			rs[idx]=idx+1;
			add(nars,ver,p,x);
		}
	}
	// u v 为node，l，r为区间，k为区间第k小（实际上来说，表示区间的是u，v。l，r为值域）
	int query(int u,int v,int l,int r,int k){
		if(l==r){
			if(sum[v]-sum[u]>=k) return l;
			else return INF;
		}
		// 我们这样就知道了
		int lsum=sum[ls[v]]-sum[ls[u]];
		int mid=l+r>>1;
		int ans1=INF,ans2=INF;
		if(lsum>=k){
			ans1=query(ls[u],ls[v],l,mid,k);
		}
		if(ans1==INF && sum[rs[v]]-sum[rs[u]]>=k){
			ans2=query(rs[u],rs[v],mid+1,r,k);
		}
		// ans1= ans1==0?INF:ans1;ans2= ans2==0?INF:ans2;
		return min(ans1,ans2);
	}
};
persisTree tr;
inline void solve(){
	scanf("%lld%lld",&N,&M);
	FOR(i,1,N){
		scanf("%d",&tr.arr[i]);
	}
	int len=tr.initLi(N,N);
	tr.build(1,1,len);
	FOR(i,1,N){
		tr.add(tr.root[i-1],i-1,tr.kth(tr.arr[i]),1);
	}
	tr.li[0]=-1;
	FOR(_,1,M){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		int mid=(r-l+1)/k+1;
		// int pos=tr.kth(mid);
		int ans=tr.query(tr.root[l-1],tr.root[r],1,len,mid);
		ans= ans==INF?-1:tr.li[ans];
		printf("%d\n",ans);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/840/submission/321605622
*/

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

P3567 [POI 2014] KUR-快递员（区间内有没有一个数出现次数超过一半）

Posted on 2025-05-27 Edited on 2026-02-17

思路讲解

给一个数列，每次询问一个区间内有没有一个数出现次数超过一半。

AC代码

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

源代码

// Problem: P3567 [POI 2014] KUR-Couriers
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3567
// 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.front())
#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 __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(5e5)+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];
/*

*/
struct persisTree{	// 单点修改区间查询的主席树，处理静态区间第 k 小问题。
	// 由于太大了，该结构体只能声明与全局变量作用域
	// 测试 https://www.luogu.com.cn/record/218615977 （只测了单次数据）
	// maxn为点的数量，maxm为版本数量（在静态区间第 k 小问题中，和maxn一样）
	static const int maxn=static_cast<int>(5e5)+7,maxm=static_cast<int>(5e5)+7;
	static const int LOGmxm=19;		// 这个版本次数一般也不会超过2**20，也就是1048576
	static const int maxn4=maxn*4+LOGmxm*maxn;
	int ls[maxn4],rs[maxn4],L[maxn4],R[maxn4],root[maxm];
	int arr[maxn],sum[maxn4];
	int n=0,m=0,idx=1,Cver=0,len=0;
	int li[maxn];	
	// root为不同版本的根。L，R为左端点 右端点，ls rs 为左孩子 右孩子，arr为原数组。
	inline void init(int ln,int lm){
		// int lmaxn4=ln*4+log2(ln)*lm+5;
		idx=1,n=ln,m=lm,Cver=0;
		root[0]=1;	// 版本0的根是1
	}
	inline int initLi(){	// 离散化操作
		for(int i=1;i<=n;++i){
			li[i]=arr[i];
		}
		sort(li+1,li+1+n);
		len=unique(li+1,li+1+n)-li-1;	// 这个len是超了一个的
		return len;
	}
	inline int kth(ll x){
		int ret=lower_bound(li+1,li+1+len,x)-li;
		return ret;
	}
	inline void clone(int node){
		++idx;
		L[idx]=L[node];
		R[idx]=R[node];
		sum[idx]=sum[node];
		ls[idx]=ls[node];
		rs[idx]=rs[node];
	}
	void build(int node,int l,int r){
		ls[node]=++idx;
		rs[node]=++idx;
		L[node]=l;
		R[node]=r;
		sum[node]=0;
		if(l==r) return;
		build(ls[node],l,((l+r)>>1));
		build(rs[node],(l+r>>1)+1,r);
	}
	// 处理静态区间第 k 小问题中，因为权值线段树，x=1
	void add(int node,int ver,int p,ll x){ 	
		clone(node);
		sum[idx]+=x;
		// 如果当前遍历到的点是一个版本的根，那么现在的点idx就是目前这个版本的根
		if(root[ver]==node){	
			++Cver;
			root[Cver]=idx;
		}
		if(p==L[node] && p==R[node]){
			return;
		}
		if(p>=L[ls[node]] && p<=R[ls[node]]){
			int nals=ls[idx];
			ls[idx]=idx+1;
			add(nals,ver,p,x);
		}else{
			int nars=rs[idx];
			rs[idx]=idx+1;
			add(nars,ver,p,x);
		}
	}
	// 我们要查询是否有一个数出现次数超过一半
	int query(int u,int v,int l,int r,int k){
// #ifdef LOCAL
	// debug(u);
	// debug(L[u]);
	// debug(R[u]);
	// debug(sum[u]);
	// debug(v);
	// debug(L[v]);
	// debug(R[v]);
	// debug(sum[v]);
// 	
// #endif
		if(l==r){
			if(sum[v]-sum[u]>=k) return l;
			else return 0;
		}
		// 我们这样就知道了
		int lsum=sum[ls[v]]-sum[ls[u]];
// #ifdef LOCAL
    // debug(lsum);
    // debug(k);
    // cerr<<"\n";
// #endif
		int mid=l+r>>1;
		if(lsum>=k){
			return query(ls[u],ls[v],l,mid,k);
		}else{
			return query(rs[u],rs[v],mid+1,r,k);
		}
	}
};

persisTree tr;

inline void solve(){
	// N=read(),M=read();
	scanf("%lld%lld",&N,&M);
	// cin>>N>>M;
	tr.init(N,N);
	FOR(i,1,N){
		// tr.arr[i]=read();
		scanf("%d",&tr.arr[i]);
	}
	int len=tr.initLi();
	tr.build(1,1,len);
	FOR(i,1,N){
		tr.add(tr.root[i-1],i-1,tr.kth(tr.arr[i]),1);
	}
	FOR(_,1,M){
		// ll l=read(),r=read();
		ll l,r;
		scanf("%lld%lld",&l,&r);
		ll mid=(r-l+1)/2+1;
// #ifdef LOCAL
    // debug(mid);
// #endif
		int ans=tr.li[tr.query(tr.root[l-1],tr.root[r],1,len,mid)];
		// write(ans);
		// putchar('\n');
		// cout<<ans<<"\n";
		printf("%d\n",ans);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/218724163

1 1
1
1 1

*/

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

我超，这个POI的数据还是挺严格的，我的这个主席树codeforces和洛谷模版都过了，就这道题目没有过。

1
2
3

1 1
1
1 1

黑体部分，要放在比较下面，不要放在版本更新的上面，否则可能未版本更新就出去了。

// 处理静态区间第 k 小问题中，因为权值线段树，x=1
void add(int node,int ver,int p,ll x){ 	
	clone(node);
	sum[idx]+=x;
	// 如果当前遍历到的点是一个版本的根，那么现在的点idx就是目前这个版本的根
	if(root[ver]==node){	
		++Cver;
		root[Cver]=idx;
	}
	if(p==L[node] && p==R[node]){
		return;
	}
	if(p>=L[ls[node]] && p<=R[ls[node]]){
		int nals=ls[idx];
		ls[idx]=idx+1;
		add(nals,ver,p,x);
	}else{
		int nars=rs[idx];
		rs[idx]=idx+1;
		add(nars,ver,p,x);
	}
}

P3834 【模板】可持久化线段树 2

Posted on 2025-05-26 Edited on 2026-02-17

思路讲解

主要参考这段代码

https://github.com/algorithmzuo/algorithm-journey/blob/main/src/class157/Code02_PointPersistent2.java

参考题解

【算法讲解157【挺难】可持久化线段树和标记永久化】【精准空降到 45:11】 https://www.bilibili.com/video/BV1bSc6eREi4/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=2711

AC代码

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

源代码

// Problem: P3834 【模板】可持久化线段树 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3834
// Memory Limit: 1 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.front())
#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 __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
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;
/*

*/
struct persisTree{	// 单点修改区间查询的主席树，处理静态区间第 k 小问题。
	// 由于太大了，该结构体只能声明与全局变量作用域
	// // maxn为点的数量，maxm为版本数量（在静态区间第 k 小问题中，和maxn一样）
	static const int maxn=static_cast<ll>(2e5)+7,maxm=static_cast<ll>(2e5)+7;
	static const int maxn4=maxn*22;		// 这个版本次数一般也不会超过int，给个32绝对够了
	int ls[maxn4],rs[maxn4],L[maxn4],R[maxn4],root[maxm];
	ll arr[maxn],sum[maxn4];
	int n=0,m=0,idx=1,Cver=0,len=0;
	ll li[maxn];	
	// root为不同版本的根。L，R为左端点 右端点，ls rs 为左孩子 右孩子，arr为原数组。
	// vector<int> ls,rs,L,R,root,arr,li;	// 因为主席树这些数是不能复用的，我们直接就用动态数组吧。
	// persisTree(int ln,int lm){
		// n=ln,m=lm;
		// ll siz=n*4+log2(n)*m+7;
		// ls.resize(siz),rs.resize(siz),L.resize(siz),R.resize(siz),root.resize(siz);
		// arr.resize(siz);
	// }
	inline void init(int ln,int lm){
		// int lmaxn4=ln*4+log2(ln)*lm+5;
		idx=1,n=ln,m=lm,Cver=0;
		// for(int i=0;i<=lmaxn4;++i){	// 有build在，init不用干这个事情
			// ls[i]=0,rs[i]=0;
			// sum[i]=0,L[i]=0,R[i]=0;
		// }
		// for(int i=0;i<=lm;++i){
			// root[i]=0,arr[i]=0;
		// }
		root[0]=1;	// 版本0的根是1
	}
	inline int initLi(){	// 离散化操作
		for(int i=1;i<=n;++i){
			li[i]=arr[i];
		}
		sort(li+1,li+1+n);
		len=unique(li+1,li+1+n)-li-1;	// 这个len是超了一个的
		return len;
	}
	inline int kth(ll x){
		int ret=lower_bound(li+1,li+1+len,x)-li;
		return ret;
	}
	inline void clone(int node){
		++idx;
		L[idx]=L[node];
		R[idx]=R[node];
		sum[idx]=sum[node];
		ls[idx]=ls[node];
		rs[idx]=rs[node];
	}
	void build(int node,int l,int r){
		ls[node]=++idx;
		rs[node]=++idx;
		L[node]=l;
		R[node]=r;
		sum[node]=0;
		if(l==r) return;
		build(ls[node],l,((l+r)>>1));
		build(rs[node],(l+r>>1)+1,r);
	}
	// 处理静态区间第 k 小问题中，因为权值线段树，x=1
	void add(int node,int ver,int p,ll x){ 	
		clone(node);
		sum[idx]+=x;
		if(p==L[node] && p==R[node]){
			return;
		}
		// 如果当前遍历到的点是一个版本的根，那么现在的点idx就是目前这个版本的根
		if(root[ver]==node){	
			++Cver;
			root[Cver]=idx;
		}
		if(p>=L[ls[node]] && p<=R[ls[node]]){
			int nals=ls[idx];
			ls[idx]=idx+1;
			add(nals,ver,p,x);
		}else{
			int nars=rs[idx];
			rs[idx]=idx+1;
			add(nars,ver,p,x);
		}
	}
	// u v 为node，l，r为区间，k为区间第k小
	int query(int u,int v,int l,int r,int k){
		if(l==r){
			return l;
		}
		// 我们这样就知道了
		int lsum=sum[ls[v]]-sum[ls[u]];
		int mid=l+r>>1;
		if(lsum>=k){
			return query(ls[u],ls[v],l,mid,k);
		}else{
			return query(rs[u],rs[v],mid+1,r,k-lsum);
		}
	}
};

inline ll read()
{
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{
			if(ch=='-')
				f=-1;
			ch=getchar();
		}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}
void write(ll x)
{
	if(x<0)
		putchar('-'),x=-x;
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
	return;
}

persisTree tr;	// 由于太大了，该结构体只能声明与全局变量作用域

inline void solve(){
	N=read(),M=read();
	tr.init(N,N);
	FOR(i,1,N){
		tr.arr[i]=read();
	}
	int len=tr.initLi();
// #ifdef LOCAL
    // cerr << "build 1" << '\n';
// #endif
	tr.build(1,1,len);
// #ifdef LOCAL
    // cerr << "build 2" << '\n';
// #endif
	FOR(i,1,N){
		// 权值线段树单点加
		tr.add(tr.root[tr.Cver],tr.Cver,tr.kth(tr.arr[i]),1);
// #ifdef LOCAL
	// debug(tr.kth(tr.arr[i]));
    // FOR(i,1,tr.idx){
    	// cerr<<i<<" L:"<<tr.L[i]<<" R:"<<tr.R[i]<<" sum:"<<tr.sum[i]<<"\n";
    // }
    // cerr<<"\n";
// #endif
// #ifdef LOCAL
    // debug(i);
// #endif
	}
// #ifdef LOCAL
    // cerr << "success add" << '\n';
// #endif
	FOR(_,1,M){
		ll l=read(),r=read(),k=read();
		// 这个l,r是权值线段树中的值域，所以初始传入【1，2】
		ll ans=tr.query(tr.root[l-1],tr.root[r],1,len,k);
		write(tr.li[ans]),putchar('\n');
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/218615977
*/

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

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

这个 k-lsum 要小心，记得要加，因为往r走相当于抛掉了一些东西

// u v 为node，l，r为区间，k为区间第k小
int query(int u,int v,int l,int r,int k){
	if(l==r){
		return l;
	}
	// 我们这样就知道了
	int lsum=sum[ls[v]]-sum[ls[u]];
	int mid=l+r>>1;
	if(lsum>=k){
		return query(ls[u],ls[v],l,mid,k);
	}else{    // 这个 k-lsum 要小心，记得要加，因为往r走相当于抛掉了一些东西
		return query(rs[u],rs[v],mid+1,r,k-lsum);
	}
}

【LGR-225-Div.1.5】洛谷蓝桥杯模拟赛 P12594 炽声音节旋

Posted on 2025-05-26 Edited on 2026-02-17

思路讲解

字符串转化为数字函数（stoi）的使用。

https://en.cppreference.com/w/cpp/string/basic_string/stol

AC代码

源代码