登录
← 返回首页 | 代码片段 › 2 数据结构 › 2.7 平衡树 › 平衡树 / 搜索
JSON MD

2.7 平衡树

平衡树 BalancedBST
280 行
CPP JSON
【平衡二叉搜索树(AVL 树)模板】 ▪ TreeNode — 节点结构,维护 key(键值)、height(高度)、size(子树大小)、count(重复计数) ▪ getHeight(node) / getSize(node) — 获取节点高度/子树大小(空节点返回 0) ▪ updateNodeInfo(node) — 更新节点的高度和子树大小(插入/旋转后调用) ▪ getBalanceFactor(node) — 获取平衡因子(左高 - 右高),用于判断是否需要旋转 ▪ rightRotate(y) / leftRotate(x) — 右旋/左旋操作,保持 AVL 平衡 ▪ balanceNode(node) — 综合平衡调整(根据平衡因子选择 LL/LR/RR/RL 四种旋转) 所有操作(插入、删除、查找第 k 小/大、查询排名)均为 O(log N)。
C++ 280 行 CPP
struct TreeNode {
    int key;
    TreeNode* left;
    TreeNode* right;
    int height; // 节点高度
    int size;   // 子树大小
    int count;  // 重复次数

    TreeNode(int value) 
        : key(value), height(1), size(1), count(1), left(nullptr), right(nullptr) {}
};

class BalancedBST {
private:
    TreeNode* root;

    // 获取节点高度
    int getHeight(TreeNode* node) const {
        return node ? node->height : 0;
    }

    // 获取节点子树大小
    int getSize(TreeNode* node) const {
        return node ? node->size : 0;
    }

    // 更新节点高度和大小
    void updateNodeInfo(TreeNode* node) const {
        if (node) {
            node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
            node->size = node->count + getSize(node->left) + getSize(node->right);
        }
    }

    // 获取平衡因子
    int getBalanceFactor(TreeNode* node) const {
        return node ? getHeight(node->left) - getHeight(node->right) : 0;
    }

    // 右旋
    TreeNode* rightRotate(TreeNode* y) const {
        TreeNode* x = y->left;
        TreeNode* T2 = x->right;

        x->right = y;
        y->left = T2;

        updateNodeInfo(y);
        updateNodeInfo(x);

        return x;
    }

    // 左旋
    TreeNode* leftRotate(TreeNode* x) const {
        TreeNode* y = x->right;
        TreeNode* T2 = y->left;

        y->left = x;
        x->right = T2;

        updateNodeInfo(x);
        updateNodeInfo(y);

        return y;
    }

    // 平衡节点
    TreeNode* balanceNode(TreeNode* node) const {
        if (!node) return nullptr;

        updateNodeInfo(node);
        int balance = getBalanceFactor(node);

        // Left Left Case
        if (balance > 1 && getBalanceFactor(node->left) >= 0)
            return rightRotate(node);

        // Right Right Case
        if (balance < -1 && getBalanceFactor(node->right) <= 0)
            return leftRotate(node);

        // Left Right Case
        if (balance > 1 && getBalanceFactor(node->left) < 0) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }

        // Right Left Case
        if (balance < -1 && getBalanceFactor(node->right) > 0) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }

    // 递归插入
    TreeNode* insertHelper(TreeNode* node, int value){
        if (!node) {
            return new TreeNode(value);
        }

        if (value < node->key) {
            node->left = insertHelper(node->left, value);
        } else if (value > node->key) {
            node->right = insertHelper(node->right, value);
        } else {
            node->count++;
            node->size++;
            return node;
        }

        return balanceNode(node);
    }

    // 查找最小节点
    TreeNode* findMinNode(TreeNode* node) const {
        while (node && node->left) {
            node = node->left;
        }
        return node;
    }

    // 递归删除
    TreeNode* removeHelper(TreeNode* node, int value){
        if (!node) return nullptr;

        if (value < node->key) {
            node->left = removeHelper(node->left, value);
        } else if (value > node->key) {
            node->right = removeHelper(node->right, value);
        } else {
            if (node->count > 1) {
                node->count--;
                node->size--;
                return node;
            }

            if (!node->left || !node->right) {
                TreeNode* temp = node->left ? node->left : node->right;
                if (!temp) {
                    delete node;
                    return nullptr;
                } else {
                    *node = *temp;
                    delete temp;
                }
            } else {
                TreeNode* successor = findMinNode(node->right);
                node->key = successor->key;
                node->count = successor->count;
                successor->count = 1;
                node->right = removeHelper(node->right, successor->key);
            }
        }

        return balanceNode(node);
    }

    // 递归查找
    bool searchHelper(TreeNode* node, int value) const {
        if (!node) return false;
        if (value == node->key) return true;
        if (value < node->key) return searchHelper(node->left, value);
        return searchHelper(node->right, value);
    }

    // 递归中序遍历
    void inorderHelper(TreeNode* node, std::vector<int>& result) const {
        if (!node) return;
        inorderHelper(node->left, result);
        for (int i = 0; i < node->count; ++i) {
            result.push_back(node->key);
        }
        inorderHelper(node->right, result);
    }

    // 递归查询排名
    int rankHelper(TreeNode* node, int value) const {
        if (!node) return 0;
        
        if (value < node->key) {
            return rankHelper(node->left, value);
        } else if (value > node->key) {
            return getSize(node->left) + node->count + rankHelper(node->right, value);
        } else {
            return getSize(node->left) + 1;
        }
    }

    // 递归按排名查找
    int selectHelper(TreeNode* node, int k) const {
        if (!node) return -1;
        
        int leftSize = getSize(node->left);
        
        if (k <= leftSize) {
            return selectHelper(node->left, k);
        } else if (k <= leftSize + node->count) {
            return node->key;
        } else {
            return selectHelper(node->right, k - leftSize - node->count);
        }
    }

    // 递归释放所有节点
    void clearHelper(TreeNode* node) {
        if (!node) return;
        clearHelper(node->left);
        clearHelper(node->right);
        delete node;
    }

public:
    BalancedBST() : root(nullptr) {}

    // 插入元素 - O(log n)
    void insert(int value) {
        root = insertHelper(root, value);
    }

    // 删除元素 - O(log n)
    void remove(int value) {
        root = removeHelper(root, value);
    }

    // 查找元素 - O(log n)
    bool search(int value) const {
        return searchHelper(root, value);
    }

    // 获取最小值 - O(log n)
    int min() const {
        TreeNode* node = findMinNode(root);
        return node ? node->key : -1;
    }

    // 获取最大值 - O(log n)
    int max() const {
        TreeNode* node = root;
        while (node && node->right) {
            node = node->right;
        }
        return node ? node->key : -1;
    }

    // 中序遍历 - O(n)
    std::vector<int> inorder() const {
        std::vector<int> result;
        inorderHelper(root, result);
        return result;
    }

    // 查询排名 - O(log n)
    int rank(int value) const {
        return rankHelper(root, value);
    }

    // 按排名查找 - O(log n)
    int select(int k) const {
        return selectHelper(root, k);
    }

    // 清空整棵树
    void clear() {
        clearHelper(root);
        root = nullptr;
    }

    // 获取树的大小 - O(1)
    int size() const {
        return getSize(root);
    }

    // 获取树的高度 - O(1)
    int height() const {
        return getHeight(root);
    }
};
Splay (无注释)(文艺平衡树) 区间翻转
77 行
CPP JSON
【Splay (无注释)(文艺平衡树)(区间翻转)】 Splay(伸展树)模板,通过伸展操作实现均摊高效访问。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void connect(Re p,Re f,Re o) — 核心算法函数 int which(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 void rotate(Re p) — 旋转操作(平衡树) void Splay(Re p,Re to) — 伸展操作(Splay树) void New(Re x,Re fa) — 核心算法函数 核心结构体:Splay 关键配置: N=1e5+5,inf=2e9 复杂度:所有操作 O(log N) 适用场景:有序集合维护、第K小查询、排名/前驱/后继查询
C++ 76 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#define Re register int
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int T,x,y,n,o,root,a[N];
struct Splay{int v,fa,ps[2],tag,cnt,size;}tr[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void pushup(Re p){if(!p)return;tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void connect(Re p,Re f,Re o){tr[tr[p].fa=f].ps[o]=p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void pushdown(Re p){
	if(tr[p].tag)tr[p].tag=0,swap(pl,pr),tr[pl].tag^=1,tr[pr].tag^=1;
} 
inline void rotate(Re p){
	Re y=pf,ys=which(p);
	Re R=tr[y].fa,Rs=which(y);
	Re B=tr[p].ps[ys^1];
	connect(B,y,ys),connect(y,p,ys^1),connect(p,R,Rs);
	pushup(y),pushup(p);
}
inline void Splay(Re p,Re to){
	for(Re fa;(fa=pf)!=to;rotate(p))
		if(tr[fa].fa!=to)rotate(which(p)==which(fa)?fa:p);
	if(!to)root=p;
}
inline void New(Re x,Re fa){
	tr[++o].v=x,tr[o].fa=fa,tr[o].cnt=tr[o].size=1;
	if(fa)tr[fa].ps[tr[fa].v<x]=o;
}
inline int ask_w(Re p,Re x){
	pushdown(p);
	if(x<=tr[pl].size)return ask_w(pl,x);
	else{
		Re tmp=tr[pl].size+tr[p].cnt;
		return x<=tmp?p:ask_w(pr,x-tmp);
	}
}
inline void build(Re &p,Re L,Re R,Re fa){
	if(L>R)return;
	Re mid=L+R>>1;p=++o;
	pf=fa,pv=a[mid];
	tr[p].cnt=tr[p].size=1;
	build(pl,L,mid-1,p),build(pr,mid+1,R,p);
	pushup(p);
}
inline void reverse(Re l,Re r){
	l=ask_w(root,l-1),r=ask_w(root,r+1);
	Splay(l,0),Splay(r,l);
	tr[tr[r].ps[0]].tag^=1;
}
inline void print(Re p){
	pushdown(p);
	if(pl)print(pl);
	if(pv!=inf&&pv!=-inf)printf("%d ",pv);
	if(pr)print(pr);
}
int main(){
	in(n),in(T);
	a[1]=-inf,a[n+2]=inf;
	for(Re i=2;i<=n+1;++i)a[i]=i-1;
	build(root,1,n+2,0);
	while(T--)in(x),in(y),reverse(x+1,y+1);
	print(root);
}
Splay (有注释)(文艺平衡树) 区间翻转
77 行
CPP JSON
【Splay (有注释)(文艺平衡树)(区间翻转)】 Splay(伸展树)模板,通过伸展操作实现均摊高效访问。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void connect(Re p,Re f,Re o) — 核心算法函数 int which(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 void rotate(Re p) — 旋转操作(平衡树) void Splay(Re p,Re to) — 伸展操作(Splay树) void New(Re x,Re fa) — 核心算法函数 核心结构体:Splay 关键配置: N=1e5+5,inf=2e9 复杂度:所有操作 O(log N) 说明:��l~rȫ���Ƶ� ��(l-1)�� �����Ҷ���(r+1)�м䣬�������IJ��� 适用场景:有序集合维护、第K小查询、排名/前驱/后继查询
C++ 76 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#define Re register int
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int T,x,y,n,o,root,a[N];
struct Splay{int v,fa,ps[2],tag,cnt,size;}tr[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void pushup(Re p){if(!p)return;tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void connect(Re p,Re f,Re o){tr[tr[p].fa=f].ps[o]=p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void pushdown(Re p){
    if(tr[p].tag)tr[p].tag=0,swap(pl,pr),tr[pl].tag^=1,tr[pr].tag^=1;
} 
inline void rotate(Re p){
    Re y=pf,ys=which(p);
    Re R=tr[y].fa,Rs=which(y);
    Re B=tr[p].ps[ys^1];
    connect(B,y,ys),connect(y,p,ys^1),connect(p,R,Rs);
    pushup(y),pushup(p);
}
inline void Splay(Re p,Re to){
    for(Re fa;(fa=pf)!=to;rotate(p))
        if(tr[fa].fa!=to)rotate(which(p)==which(fa)?fa:p);
    if(!to)root=p;
}
inline void New(Re x,Re fa){
    tr[++o].v=x,tr[o].fa=fa,tr[o].cnt=tr[o].size=1;
    if(fa)tr[fa].ps[tr[fa].v<x]=o;
}
inline int ask_w(Re p,Re x){
    pushdown(p);
    if(x<=tr[pl].size)return ask_w(pl,x);
    else{
        Re tmp=tr[pl].size+tr[p].cnt;
        return x<=tmp?p:ask_w(pr,x-tmp);
    }
}
inline void build(Re &p,Re L,Re R,Re fa){
    if(L>R)return;
    Re mid=L+R>>1;p=++o;
    pf=fa,pv=a[mid];
    tr[p].cnt=tr[p].size=1;
    build(pl,L,mid-1,p),build(pr,mid+1,R,p);
    pushup(p);
}
inline void reverse(Re l,Re r){
    l=ask_w(root,l-1),r=ask_w(root,r+1);
    Splay(l,0),Splay(r,l);
    tr[tr[r].ps[0]].tag^=1;
}
inline void print(Re p){
    pushdown(p);
    if(pl)print(pl);
    if(pv!=inf&&pv!=-inf)printf("%d ",pv);
    if(pr)print(pr);
}
int main(){
    in(n),in(T);
    a[1]=-inf,a[n+2]=inf;
    for(Re i=2;i<=n+1;++i)a[i]=i-1;
    build(root,1,n+2,0);
    while(T--)in(x),in(y),reverse(x+1,y+1);
    print(root);
}
Splay 数列P2710
134 行
CPP JSON
【Splay(数列P2710)】 Splay(伸展树)模板,通过伸展操作实现均摊高效访问。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void updata(Re p,Re v) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Splay, QAQ 关键配置: N=2e5+3,inf=1e9 复杂度:所有操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:有序集合维护、第K小查询、排名/前驱/后继查询
C++ 133 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5+3,inf=1e9;
int n,x,y,z,T,A[N];char op[20];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Splay{
	#define pl (tr[p].ps[0])
	#define pr (tr[p].ps[1])
	#define pf (tr[p].fa)
	#define pv (tr[p].v)
	int O,root,Q[N];queue<int>D;
	struct QAQ{int v,S,fa,max,lmax,rmax,size,ps[2];bool tag,turn;}tr[N];
	inline void pushup(Re p){
		tr[p].S=tr[pl].S+tr[pr].S+pv;
		tr[p].size=tr[pl].size+tr[pr].size+1;
		tr[p].lmax=max(tr[pl].lmax,tr[pl].S+pv+tr[pr].lmax);
		tr[p].rmax=max(tr[pr].rmax,tr[pr].S+pv+tr[pl].rmax);
		tr[p].max=max(tr[pl].rmax+pv+tr[pr].lmax,max(tr[pl].max,tr[pr].max));
	}
	inline void updata(Re p){tr[p].turn^=1,swap(pl,pr),swap(tr[p].lmax,tr[p].rmax);}
	inline void updata(Re p,Re v){
		tr[p].tag=1,tr[p].S=(pv=v)*tr[p].size;
		if(v>0)tr[p].lmax=tr[p].rmax=tr[p].max=tr[p].S;
		else tr[p].lmax=tr[p].rmax=0,tr[p].max=v;
	}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl,pv);
			if(pr)updata(pr,pv);
			tr[p].tag=tr[p].turn=0;
		}
		if(tr[p].turn){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].turn=0;
		}
	}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		connect(x,fa,fas),connect(fa,p,fas^1),connect(p,pa,pas);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p,Re to){
		Re x=p,t=0;Q[++t]=x;
		while(tr[x].fa)Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;pf!=to;rotate(p))
			if(tr[fa=pf].fa!=to)rotate(which(p)==which(fa)?fa:p);
		if(!to)root=p;
	}
	inline void CL(Re p){
		tr[p].size=tr[p].turn=tr[p].tag=tr[p].lmax=tr[p].rmax=tr[p].S=pv=pf=pl=pr=0,tr[p].max=-inf;
	}
	inline int New(){
		Re p;
		if(D.empty())p=++O;
		else p=D.front(),D.pop();
		CL(p),tr[p].size=1;return p;
	}
	inline void build(Re &p,Re L,Re R,Re fa){
		if(L>R)return;Re mid=(L+R)>>1;p=New(),pv=A[mid],pf=fa;
		build(pl,L,mid-1,p),build(pr,mid+1,R,p);
		pushup(p);
	}
	inline void recycle(Re p){
		if(pl)recycle(pl);
		if(pr)recycle(pr);
		D.push(p),CL(p);
	}
	inline int find(Re p,Re K){
		pushdown(p);
		if(K<=tr[pl].size)return find(pl,K);
		return K<=tr[pl].size+1?p:find(pr,K-tr[pl].size-1);
	}
	inline int split(Re L,Re R){
		Re p=find(root,L-1),q=find(root,R+1);
		splay(p,0),splay(q,p);return tr[q].ps[0];
	}
	inline void insert(Re st,Re m){
		for(Re i=1;i<=m;++i)in(A[i]);
		Re rt=0;build(rt,1,m,0);
		Re p=find(root,st),q=find(root,st+1);
		splay(p,0),splay(q,p);
		connect(rt,q,0),pushup(q),pushup(p);
	}
	inline void erase(Re L,Re R){
		Re p=split(L,R),fa=pf;
		tr[fa].ps[0]=pf=0,recycle(p);
		pushup(fa),pushup(tr[fa].fa);
	}
	inline int ask(Re L,Re R){return tr[split(L,R)].S;}
	inline int ask_max(Re L,Re R){return tr[split(L,R)].max;}
	inline void change(Re L,Re R,Re v){
		Re p=split(L,R);updata(p,v),pushup(pf),pushup(tr[pf].fa);
	}
	inline void reverse(Re L,Re R){
		Re p=split(L,R);
		if(!tr[p].tag)updata(p),pushup(pf),pushup(tr[pf].fa);
	}
}TR;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(T),TR.tr[0].max=A[1]=A[n+2]=-inf;
	for(Re i=2;i<=n+1;++i)in(A[i]);
	TR.build(TR.root,1,n+2,0);
	while(T--){
		scanf("%s",op);
        if(op[0]=='M'&&op[2]=='X')in(x),in(y),++x,printf("%d\n",TR.ask_max(x,x+y-1));
		else if(op[0]=='G'&&(int)strlen(op)==3)in(x),++x,printf("%d\n",TR.ask(x,x));
		else{
			in(x),in(y),++x;
	        if(op[0]=='I')TR.insert(x,y);
	        if(op[0]=='D')TR.erase(x,x+y-1);
	        if(op[0]=='M')in(z),TR.change(x,x+y-1,z);
	        if(op[0]=='R')TR.reverse(x,x+y-1);
	        if(op[0]=='G')printf("%d\n",TR.ask(x,x+y-1));
		}
	}
}
Splay (无注释) 普通平衡树
86 行
CPP JSON
【Splay (无注释)(普通平衡树)】 Splay(伸展树)模板,通过伸展操作实现均摊高效访问。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) void splay(Re p) — 伸展操作(Splay树) int ask_level(Re p,Re x) — 核心算法函数 int ask_v(Re p,Re k) — 核心算法函数 核心结构体:Splay, QAQ 关键配置: N=1e5+5 复杂度:所有操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:有序集合维护、第K小查询、排名/前驱/后继查询
C++ 85 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=1e5+5;
int x,T,op;
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Splay{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	#define pv tr[p].v
	int O,root;
	struct QAQ{int v,fa,cnt,size,ps[2];}tr[N];
	inline void pushup(Re p){
		if(p)tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;
	}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		connect(x,fa,fas),connect(fa,p,fas^1),connect(p,pa,pas);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		for(Re fa;fa=pf;rotate(p))
			if(tr[fa].fa)rotate(which(p)==which(fa)?fa:p);
		root=p;
	}
	inline int ask_level(Re p,Re x){
		if(x==pv){Re ans=tr[pl].size+1;splay(p);return ans;}
		return x<pv?ask_level(pl,x):tr[pl].size+tr[p].cnt+ask_level(pr,x);
	}
	inline int ask_v(Re p,Re k){
		if(!p)return 0;
		if(k<=tr[pl].size)return ask_v(pl,k);
		Re tmp=tr[pl].size+tr[p].cnt;
		return k<=tmp?pv:ask_v(pr,k-tmp);
	}
	inline int pre(Re p){p=pl;while(pr)p=pr;return p;}
	inline int nex(Re p){p=pr;while(pl)p=pl;return p;}
	inline void insert(Re x){
		Re p=root,fa=0;
		while(p&&pv!=x)fa=p,p=tr[p].ps[x>pv];
		if(p)++tr[p].cnt,pushup(p);
		else{
			tr[p=++O]=(QAQ){x,fa,1,1};
			if(fa)tr[fa].ps[x>tr[fa].v]=p;
		}
		splay(p);
	}
	inline void del(Re x){
		ask_level(root,x);Re p=root;
		if(tr[p].cnt>1){--tr[p].cnt,pushup(p);return;}
		if(!pl&&!pr){root=0;return;}
		if(!pl||!pr){tr[root=pl+pr].fa=0;return;}
		splay(pre(p));
		tr[root].ps[1]=pr,tr[pr].fa=root;
		pushup(root);
	}
	inline int ask_pre(Re x){insert(x);Re ans=tr[pre(root)].v;del(x);return ans;}
	inline int ask_nex(Re x){insert(x);Re ans=tr[nex(root)].v;del(x);return ans;}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(T);
	while(T--){
		in(op),in(x);
		if(op==1)T1.insert(x);
		if(op==2)T1.del(x);
		if(op==3)printf("%d\n",T1.ask_level(T1.root,x));
		if(op==4)printf("%d\n",T1.ask_v(T1.root,x));
		if(op==5)printf("%d\n",T1.ask_pre(x));
		if(op==6)printf("%d\n",T1.ask_nex(x));
	}
}
Splay (有注释) 普通平衡树
83 行
CPP JSON
#pragma GCC optimize(3,"Ofast","inline") #pragma GCC optimize(2)
C++ 82 行 CPP
//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#define Re register int
#define pl tr[p].ps[0]
#define pr tr[p].ps[1]
#define pf tr[p].fa 
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int T,a,b,n,o,root;
struct Splay{int v,fa,ps[2],cnt,size;}tr[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void pushup(Re p){if(!p)return;/*�������Ҫ���ж�return����������*/tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void connect(Re p,Re f,Re o){tr[tr[p].fa=f].ps[o]=p;}
inline int which(Re p){return tr[pf].ps[1]==p;}
inline void rotate(Re p){
	Re y=pf,ys=which(p);
	Re R=tr[y].fa,Rs=which(y);
	Re B=tr[p].ps[ys^1];
	connect(B,y,ys),connect(y,p,ys^1),connect(p,R,Rs);
	pushup(y),pushup(p);
}
inline void Splay(Re p){
	for(Re fa;fa=pf;rotate(p))
		if(tr[fa].fa)rotate(which(p)==which(fa)?fa:p);
	root=p;
}
inline void New(Re x,Re fa){
	tr[++o].v=x,tr[o].fa=fa,tr[o].cnt=tr[o].size=1;
	if(fa)tr[fa].ps[tr[fa].v<x]=o;
}
inline void insert(Re x){
	if(!root){New(x,0);root=o;return;}
	int p=root,fa=0;
	while(1){
		if(x==pv){++tr[p].cnt,pushup(p),pushup(fa),Splay(p);break;}
		fa=p,p=tr[p].ps[pv<x];
		if(!p){New(x,fa),pushup(fa),Splay(o);break;}
	}
}
inline int ask_level(Re p,Re x){
//printf("p: %d\n",p);exit(0);
	if(x==pv){Re ans=tr[pl].size+1;Splay(p);return ans;}
	else return x<pv?ask_level(pl,x):tr[p].cnt+tr[pl].size+ask_level(pr,x);
}
inline int ask_v(Re p,Re x){
	if(x<=tr[pl].size)return ask_v(pl,x);
	else{
		Re tmp=tr[pl].size+tr[p].cnt;
		return x<=tmp?pv:ask_v(pr,x-tmp);
	}
}
inline int ask_nex_p(Re p){p=pr;while(pl)p=pl;return p;}
inline int ask_pri_p(Re p){p=pl;while(pr)p=pr;return p;}
inline void del(Re x){
	ask_level(root,x);Re p=root;
	if(tr[p].cnt>1){--tr[p].cnt,--tr[p].size;return;}
	if(!pl&&!pr){root=0;return;}
	if(!pl||!pr){tr[root=pl+pr].fa=0;return;}
	Splay(ask_pri_p(root));
	tr[root].ps[1]=pr,tr[pr].fa=root;
	pushup(root);
}
int main(){
	in(T);
	while(T--){
		in(a),in(b);
		if(a==1)insert(b);
		if(a==2)del(b);
		if(a==3)printf("%d\n",ask_level(root,b));
		if(a==4)printf("%d\n",ask_v(root,b));
		if(a==5)insert(b),printf("%d\n",tr[ask_pri_p(root)].v),del(b);
		if(a==6)insert(b),printf("%d\n",tr[ask_nex_p(root)].v),del(b);
	}
}
Treap (无注释) 普通平衡树
96 行
CPP JSON
【Treap (无注释)(普通平衡树)】 FHQ Treap(无旋 Treap)模板,通过分裂/合并实现平衡。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void lturn(Re &p) — 核心算法函数 void rturn(Re &p) — 核心算法函数 void insert(Re &p,Re x) — 插入元素 void del(Re &p,Re x) — 核心算法函数 int ask_level(Re p,Re x) — 核心算法函数 int ask_v(Re p,Re x) — 核心算法函数 核心结构体:Treap 关键配置: N=1e5+5,inf=2e9 复杂度:所有操作 O(log N) 适用场景:有序集合维护、第K小查询、排名/前驱/后继查询
C++ 95 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm> 
#include<cstdlib> 
#include<cstdio>
#include<ctime>
#define Re register int
#define pl tr[p].lp
#define pr tr[p].rp
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int a,b,o,T,root;
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Treap{int v,rd,lp,rp,cnt,size;}tr[N];
inline void pushup(Re p){tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void lturn(Re &p){
	Re q=pr;pr=tr[q].lp,tr[q].lp=p;
	pushup(p),pushup(p=q);
}
inline void rturn(Re &p){
	Re q=pl;pl=tr[q].rp,tr[q].rp=p;
	pushup(p),pushup(p=q);
}
inline void insert(Re &p,Re x){
	if(!p){tr[p=++o].v=x,tr[p].cnt=tr[p].size=1,tr[p].rd=rand();return;}
	++tr[p].size;
	if(x==pv)++tr[p].cnt;
	else if(x<pv){
		insert(pl,x);
		if(tr[pl].rd<tr[p].rd)rturn(p);
	}
	else{
		insert(pr,x);
		if(tr[pr].rd<tr[p].rd)lturn(p);
	}
}
inline void del(Re &p,Re x){
	if(!p)return;
    if(x<pv)--tr[p].size,del(pl,x);
	else if(x>pv)--tr[p].size,del(pr,x);
	else{
		if(tr[p].cnt>1)--tr[p].cnt,--tr[p].size;
		else{
			if(pl*pr==0)p=pl+pr;
			else if(tr[pl].rd<tr[pr].rd)rturn(p),del(p,x);
			else lturn(p),del(p,x);
		}
	}
}
inline int ask_level(Re p,Re x){ 
	if(x==pv)return tr[pl].size+1;
	else return x<pv?ask_level(pl,x):tr[p].cnt+tr[pl].size+ask_level(pr,x);
}
inline int ask_v(Re p,Re x){
	if(x<=tr[pl].size)return ask_v(pl,x);
	else{
		Re tmp=tr[pl].size+tr[p].cnt;
		return x<=tmp?pv:ask_v(pr,x-tmp);
	}
}
inline int ask_pri(Re p,Re x){
	if(!p)return -inf;
	if(x<=pv)return ask_pri(pl,x);
	else return max(pv,ask_pri(pr,x));
}
inline int ask_nex(Re p,Re x){
	if(!p)return inf;
	if(x>=pv)return ask_nex(pr,x);
	else return min(pv,ask_nex(pl,x));
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
	return ;
}
int main(){
	srand((int)time(NULL));
	in(T);
	while(T--){
		in(a),in(b);
		if(a==1)insert(root,b);
		if(a==2)del(root,b);
		if(a==3)write(ask_level(root,b)),puts("");
		if(a==4)write(ask_v(root,b)),puts("");
		if(a==5)write(ask_pri(root,b)),puts(""); 
		if(a==6)write(ask_nex(root,b)),puts("");
	}
}
Treap (有注释) 普通平衡树
90 行
CPP JSON
【Treap (有注释)(普通平衡树)】 FHQ Treap(无旋 Treap)模板,通过分裂/合并实现平衡。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void lturn(Re &p) — 核心算法函数 void rturn(Re &p) — 核心算法函数 void insert(Re &p,Re x) — 插入元素 void del(Re &p,Re x) — 核心算法函数 int ask_level(Re p,Re x) — 核心算法函数 int ask_v(Re p,Re x) — 核心算法函数 核心结构体:Treap 关键配置: N=1e5+5,inf=2e9 复杂度:所有操作 O(log N) 适用场景:有序集合维护、第K小查询、排名/前驱/后继查询
C++ 89 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm> 
#include<cstdlib> 
#include<cstdio>
#include<ctime>
#define Re register int
#define pl tr[p].lp
#define pr tr[p].rp
#define pv tr[p].v
using namespace std;
const int N=1e5+5,inf=2e9;
int a,b,o,T,root;
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Treap{int v,rd,lp,rp,cnt,size;}tr[N];
inline void pushup(Re p){tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void lturn(Re &p){
	Re q=pr;pr=tr[q].lp,tr[q].lp=p;
	pushup(p),pushup(p=q);
}
inline void rturn(Re &p){
	Re q=pl;pl=tr[q].rp,tr[q].rp=p;
	pushup(p),pushup(p=q);
}
inline void insert(Re &p,Re x){
	if(!p){tr[p=++o].v=x,tr[p].cnt=tr[p].size=1,tr[p].rd=rand();return;}
	++tr[p].size;
	if(x==pv)++tr[p].cnt;
	else if(x<pv){
		insert(pl,x);
		if(tr[pl].rd<tr[p].rd)rturn(p);
	}
	else{
		insert(pr,x);
		if(tr[pr].rd<tr[p].rd)lturn(p);
	}
}
inline void del(Re &p,Re x){
	if(!p)return;
    if(x<pv)--tr[p].size,del(pl,x);
	else if(x>pv)--tr[p].size,del(pr,x);
	else{
		if(tr[p].cnt>1)--tr[p].cnt,--tr[p].size;
		else{
			if(pl*pr==0)p=pl+pr;
			else if(tr[pl].rd<tr[pr].rd)rturn(p),del(p,x);
			else lturn(p),del(p,x);
		}
	}
}
inline int ask_level(Re p,Re x){
	if(x==pv)return tr[pl].size+1;
	else return x<pv?ask_level(pl,x):tr[p].cnt+tr[pl].size+ask_level(pr,x);
}
inline int ask_v(Re p,Re x){
	if(x<=tr[pl].size)return ask_v(pl,x);
	else{
		Re tmp=tr[pl].size+tr[p].cnt;
		return x<=tmp?pv:ask_v(pr,x-tmp);
	}
}
inline int ask_pri(Re p,Re x){
	if(!p)return -inf;
	if(x<=pv)return ask_pri(pl,x);
	else return max(pv,ask_pri(pr,x));
}
inline int ask_nex(Re p,Re x){
	if(!p)return inf;
	if(x>=pv)return ask_nex(pr,x);
	else return min(pv,ask_nex(pl,x));
}
int main(){
	srand((int)time(NULL));
	in(T);
	while(T--){
		in(a),in(b);
		if(a==1)insert(root,b);
		if(a==2)del(root,b);
		if(a==3)printf("%d\n",ask_level(root,b));
		if(a==4)printf("%d\n",ask_v(root,b));
		if(a==5)printf("%d\n",ask_pri(root,b)); 
		if(a==6)printf("%d\n",ask_nex(root,b));
	}
}
二逼平衡树 (无注释) 树套树
96 行
CPP JSON
【二逼平衡树 (无注释)(树套树)】 平衡二叉搜索树模板,保证插入/删除/查找均为对数复杂度。 核心函数: void in(Re &x) — 核心算法函数 int ask_kth(Re L,Re R,Re k) — 核心算法函数 int ask_kth_pre(Re L,Re R,Re k) — 预处理函数 void add(Re &p,Re L,Re R,Re w,Re v) — 加法更新 void add_pre(Re x,Re v) — 加法更新 int ask_level(Re p,Re L,Re R,Re x) — 核心算法函数 int ask_level_pre(Re L,Re R,Re w) — 预处理函数 F(i,1,T) — 核心算法函数 核心结构体:QAQ, O_O, T_T 关键配置: N=1e5+3,inf=2147483647 复杂度:所有操作 O(log N) 适用场景:有序集合维护、第K小查询、排名/前驱/后继查询
C++ 95 行 CPP
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20]; 
struct QAQ{int g,lp,rp;}tree[N*250];
struct O_O{int l,r,k;}Q[N];
struct T_T{int i,x;}c[N];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline int ask_kth(Re L,Re R,Re k){
    if(L==R)return b[R];
    Re tmp=0;
    F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;
    F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;
    if(tmp>=k){
    	F(i,1,tl)ptl[i]=tree[ptl[i]].lp;
    	F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
    	return ask_kth(L,mid,k);
    }
    else{
    	F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
    	F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
    	return ask_kth(mid+1,R,k-tmp);
    }
}
inline int ask_kth_pre(Re L,Re R,Re k){
    tl=tr=0;
    for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];
    for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];
    return ask_kth(1,m,k);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
    if(!p)p=++cnt;tree[p].g+=v;
    if(L==R)return;
    if(w<=mid)add(pl,L,mid,w,v);
    else add(pr,mid+1,R,w,v);
}
inline void add_pre(Re x,Re v){
    Re w=lo(a[x]); 
    for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
	if(L==R)return tree[p].g; 
	if(x<=mid)return ask_level(pl,L,mid,x);
	else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
inline int ask_level_pre(Re L,Re R,Re w){
	Re ans=0;
    for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);
    for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);
    return ans;
}
int main(){
	in(n),in(T),m=n;
    F(i,1,n)in(a[i]),b[i]=a[i];
    F(i,1,T){
    	in(opt[i]);
    	if(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;
    	else{
    		in(Q[i].l),in(Q[i].r),in(Q[i].k);
    		if(opt[i]!=2)b[++m]=Q[i].k;
		}
    }
    sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
    F(i,1,n)add_pre(i,1);
    F(i,1,T){
    	if(opt[i]==1)Q[i].k=lo(Q[i].k),printf("%d\n",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);
    	if(opt[i]==2)printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));
		if(opt[i]==3)add_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);
		if(opt[i]==4){
			Re level=ask_level_pre(Q[i].l,Q[i].r,lo(Q[i].k)-1);
			if(!level)printf("%d\n",-inf);
			else printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,level));
		}
		if(opt[i]==5){
			Re level=ask_level_pre(Q[i].l,Q[i].r,lo(Q[i].k));
			if(level==Q[i].r-Q[i].l+1)printf("%d\n",inf);
			else printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,level+1));
		}
    }
}
二逼平衡树 (有注释) 树套树
101 行
CPP JSON
【二逼平衡树 (有注释)(树套树)】 平衡二叉搜索树模板,保证插入/删除/查找均为对数复杂度。 核心函数: void in(Re &x) — 核心算法函数 int ask_kth(Re L,Re R,Re k) — 核心算法函数 int ask_kth_pre(Re L,Re R,Re k) — 预处理函数 void add(Re &p,Re L,Re R,Re w,Re v) — 加法更新 void add_pre(Re x,Re v) — 加法更新 int ask_level(Re p,Re L,Re R,Re x) — 核心算法函数 int ask_level_pre(Re L,Re R,Re w) — 预处理函数 F(i,1,T) — 核心算法函数 核心结构体:QAQ, O_O, T_T 关键配置: N=1e5+3,inf=2147483647 复杂度:所有操作 O(log N) 说明:printf("%lf\n",(sizeof(tree))/1024.0/1024.0);;�������λ����ԭ����������һ�����������ֺ��ٰ�������һ�����ʹﵽ���滻��Ŀ�� 适用场景:有序集合维护、第K小查询、排名/前驱/后继查询
C++ 100 行 CPP
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20]; 
struct QAQ{int g,lp,rp;}tree[N*250];
struct O_O{int l,r,k;}Q[N];
struct T_T{int i,x;}c[N];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline int ask_kth(Re L,Re R,Re k){
    if(L==R)return b[R];
    Re tmp=0;
    F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;
    F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;
    if(tmp>=k){
    	F(i,1,tl)ptl[i]=tree[ptl[i]].lp;
    	F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
    	return ask_kth(L,mid,k);
    }
    else{
    	F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
    	F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
    	return ask_kth(mid+1,R,k-tmp);
    }
}
inline int ask_kth_pre(Re L,Re R,Re k){
    tl=tr=0;
    for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];
    for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];
    return ask_kth(1,m,k);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
    if(!p)p=++cnt;tree[p].g+=v;
    if(L==R)return;
    if(w<=mid)add(pl,L,mid,w,v);
    else add(pr,mid+1,R,w,v);
}
inline void add_pre(Re x,Re v){
    Re w=lo(a[x]);
    for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
	if(L==R)return tree[p].g; 
	if(x<=mid)return ask_level(pl,L,mid,x);
	else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
inline int ask_level_pre(Re L,Re R,Re w){
	Re ans=0;
    for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);
    for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);
    return ans;
}
int main(){
//	printf("%lf\n",(sizeof(tree))/1024.0/1024.0);
//	printf("%lf\n",(sizeof(tree)+sizeof(Q)+sizeof(c)+sizeof(a)+sizeof(b)+sizeof(pt)+sizeof(C))/1024.0/1024.0);
	in(n),in(T),m=n;
    F(i,1,n)in(a[i]),b[i]=a[i];
    F(i,1,T){
    	in(opt[i]);
    	if(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;
    	else{
    		in(Q[i].l),in(Q[i].r),in(Q[i].k);
    		if(opt[i]!=2)b[++m]=Q[i].k;
		}
    }
    sort(b+1,b+m+1);
    m=unique(b+1,b+m+1)-b-1;
    F(i,1,n)add_pre(i,1);
    F(i,1,T){
    	if(opt[i]==1)
    		Q[i].k=lo(Q[i].k),
			printf("%d\n",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);

    	if(opt[i]==2)
    		printf("%d\n",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));

		if(opt[i]==3)
			add_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);

		if(opt[i]==4){
		}

		if(opt[i]==5){
		}
    }
}
普通平衡树 树状数组
49 行
CPP JSON
【普通平衡树(树状数组)】 平衡二叉搜索树模板,保证插入/删除/查找均为对数复杂度。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re v) — 加法更新 int ask(Re x) — 核心算法函数 int ask_kth(Re k) — 核心算法函数 F(i,1,T) — 核心算法函数 F(i,1,T) — 核心算法函数 关键配置: N=1e5+3,inf=2147483647 复杂度:所有操作 O(log N) 适用场景:有序集合维护、第K小查询、排名/前驱/后继查询
C++ 48 行 CPP
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstdio>
#define Re register int
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
#define P(x) if(op[i]==x)
using namespace std;
const int N=1e5+3,inf=2147483647;
int m,T,fu,C[N],a[N],b[N],Q[N],op[N]; 
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void add(Re x,Re v){while(x<=m)C[x]+=v,x+=x&-x;}
inline int ask(Re x){
	Re ans=0;
	while(x>0)ans+=C[x],x-=x&-x;
	return ans;
}
inline int ask_kth(Re k){
	Re l=0,r=m;
	while(l<r){
		Re mid=l+r>>1;
		if(ask(mid)>=k)r=mid;
		else l=mid+1;
	}
	return b[l];
}
int main(){
	in(T); 
    F(i,1,T){
    	in(op[i]),in(Q[i]);
    	if(op[i]!=4)b[++m]=Q[i];
    }
    sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
    F(i,1,T){
    	P(1)add(lo(Q[i]),1);
    	P(2)add(lo(Q[i]),-1);
		P(3)printf("%d\n",ask(lo(Q[i])-1)+1);
		P(4)printf("%d\n",ask_kth(Q[i]));
		P(5)printf("%d\n",ask_kth(ask(lo(Q[i])-1)));
		P(6)printf("%d\n",ask_kth(ask(lo(Q[i]))+1));
    }
}
普通平衡树 线段树
62 行
CPP JSON
【普通平衡树(线段树)】 平衡二叉搜索树模板,保证插入/删除/查找均为对数复杂度。 核心函数: void in(Re &x) — 核心算法函数 int ask_kth(Re p,Re L,Re R,Re k) — 核心算法函数 void add(Re &p,Re L,Re R,Re w,Re v) — 加法更新 int ask_level(Re p,Re L,Re R,Re x) — 核心算法函数 F(i,1,T) — 核心算法函数 F(i,1,T) — 核心算法函数 核心结构体:QAQ 关键配置: N=1e5+3,inf=2147483647 复杂度:所有操作 O(log N) 适用场景:有序集合维护、第K小查询、排名/前驱/后继查询
C++ 61 行 CPP
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define pl tree[p].lp
#define pr tree[p].rp
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
using namespace std;
const int N=1e5+3,inf=2147483647;
int m,T,t,fu,cnt,root,a[N],b[N],Q[N],opt[N]; 
struct QAQ{int g,lp,rp;}tree[N<<1];
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline int ask_kth(Re p,Re L,Re R,Re k){
	if(L==R)return b[R];
    Re tmp=tree[pl].g;
    if(tmp>=k)return ask_kth(pl,L,mid,k);
    else return ask_kth(pr,mid+1,R,k-tmp);
}
inline void add(Re &p,Re L,Re R,Re w,Re v){
    if(!p)p=++cnt;tree[p].g+=v;
    if(L==R)return;
    if(w<=mid)add(pl,L,mid,w,v);
    else add(pr,mid+1,R,w,v);
}
inline int ask_level(Re p,Re L,Re R,Re x){
	if(!x)return 0;
	if(L==R)return tree[p].g;
	if(x<=mid)return ask_level(pl,L,mid,x);
	else return tree[pl].g+ask_level(pr,mid+1,R,x);
}
int main(){
	in(T); 
    F(i,1,T){
    	in(opt[i]),in(Q[i]);
    	if(opt[i]!=4)b[++m]=Q[i];
    }
    sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
    F(i,1,T){
    	if(opt[i]==1)add(root,1,m,lo(Q[i]),1);
    	if(opt[i]==2)add(root,1,m,lo(Q[i]),-1);
		if(opt[i]==3)printf("%d\n",ask_level(root,1,m,lo(Q[i])-1)+1);
		if(opt[i]==4)printf("%d\n",ask_kth(root,1,m,Q[i]));
		if(opt[i]==5){
			Re level=ask_level(root,1,m,lo(Q[i])-1);
			printf("%d\n",ask_kth(root,1,m,level));
		}
		if(opt[i]==6){
			Re level=ask_level(root,1,m,lo(Q[i]));
			printf("%d\n",ask_kth(root,1,m,level+1));
		}
    }
}
营业额统计 Treap
65 行
CPP JSON
【营业额统计(Treap)】 平衡二叉搜索树模板,保证插入/删除/查找均为对数复杂度。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void lturn(Re &p) — 核心算法函数 void rturn(Re &p) — 核心算法函数 void insert(Re &p,Re x) — 插入元素 int ask_pri(Re p,Re x) — 核心算法函数 int ask_nex(Re p,Re x) — 核心算法函数 核心结构体:Treap 关键配置: N=32780,inf=2e9 复杂度:所有操作 O(log N) 适用场景:有序集合维护、第K小查询、排名/前驱/后继查询
C++ 64 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm> 
#include<cstdlib> 
#include<cstdio>
#include<ctime>
#define Re register int
#define pl tr[p].lp
#define pr tr[p].rp
#define pv tr[p].v
using namespace std;
const int N=32780,inf=2e9;
int a,o,T,ans,root;
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Treap{int v,rd,lp,rp,cnt,size;}tr[N];
inline void pushup(Re p){tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}
inline void lturn(Re &p){
	Re q=pr;pr=tr[q].lp,tr[q].lp=p;
	pushup(p),pushup(p=q);
}
inline void rturn(Re &p){
	Re q=pl;pl=tr[q].rp,tr[q].rp=p;
	pushup(p),pushup(p=q);
}
inline void insert(Re &p,Re x){
	if(!p){tr[p=++o].v=x,tr[p].cnt=tr[p].size=1,tr[p].rd=rand();return;}
	++tr[p].size;
	if(x==pv)++tr[p].cnt;
	else if(x<pv){
		insert(pl,x);
		if(tr[pl].rd<tr[p].rd)rturn(p);
	}
	else{
		insert(pr,x);
		if(tr[pr].rd<tr[p].rd)lturn(p);
	}
}
inline int ask_pri(Re p,Re x){
	if(!p)return -inf;
	if(x==pv)return x;
	else if(x<pv)return ask_pri(pl,x);
	else return max(pv,ask_pri(pr,x));
}
inline int ask_nex(Re p,Re x){
	if(!p)return inf;
	if(x==pv)return x;
	else if(x>pv)return ask_nex(pr,x);
	else return min(pv,ask_nex(pl,x));
}
int main(){
	srand((int)time(NULL));
	in(T);--T;in(a);ans=a;insert(root,a);
	while(T--){
		in(a);
		ans+=min(abs(a-ask_pri(root,a)),abs(a-ask_nex(root,a)));
		insert(root,a);
	}
	printf("%d",ans);
}
已复制