【MOBAN】各种平衡树模板

2023-12-05 20:44:04

我太弱了，我太弱了，我太弱了！被平衡树搞爆了呀。/(ㄒoㄒ)/~~ （替罪羊、splay、vector)

题目：普通平衡树这是一道模板题。您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入 xx 数；
删除 xx 数（若有多个相同的数，因只删除一个）；
查询 xx 数的排名（若有多个相同的数，因输出最小的排名）；
查询排名为 xx 的数；
求 xx 的前趋（前趋定义为小于 xx，且最大的数）；
求 xx 的后继（后继定义为大于 xx，且最小的数）

1≤n≤10 5,−10 7≤x≤10 7 替罪羊树不是扭扭捏捏的旋转，也不是拆来拆去，合来合去。而是，如果不平衡就重构！！！我们每次扫到结点的时候，发现左右不平衡到了一定程度(例如设为0.75，那么如果左右树其中之一的size>=本树的子树总size），那么我们中序遍历，把他们压成一个序列，然后再次平衡的重构就可以了！是不是很好van?其他的操作该怎么和二叉树操作就怎么操作！替罪羊别的还好，就是遇到不平衡暴力重构注意特判删除时的空节点！！！尤其是前驱后继，应当找到严格的排名然后再搞而不能直接像其他的平衡树遍历一遍。否则你会像某SB玩家调一晚上orz

upd2021.11.27:新版splay板子借鉴自yyb的splay

struct node {
    int ff, ch[2];
} t[maxn];
void rot(int x) {
    int y = t[x].ff;
    int z = t[y].ff;
    int k = (t[y].ch[1] == x);
    t[x].ff = z;
    t[z].ch[t[z].ch[1] == y] = x;
    t[y].ch[k] = t[x].ch[k ^ 1];
    t[t[x].ch[k ^ 1]].ff = y;
    t[x].ch[k ^ 1] = y;
    t[y].ff = x;
}
void splay(int x, int goal) {
    while (t[x].ff != goal) {
        int y = t[x].ff;
        int z = t[y].ff;
        if (y != goal)
            ((t[z].ch[0] == y) ^ (t[y].ch[0] == x)) ? rot(x) : rot(y);
        rot(x);
    }
}

替罪羊树模板：

#include<bits/stdc++.h>
#define ls ch[0]
#define rs ch[1]
using namespace std;
const int maxn = 2e5+5;
int n;
struct node{
    node* ch[2];
    int dat,cnt;
    int sz,jd,fjd;//size和节点和实际存在的结点个数
}z[maxn],*pool[maxn],*nul,**rbrt,*RT;
int tot,lj;

void init() {
    RT = nul = &z[0];
    nul->ch[0] = nul->ch[1] = nul;
    rbrt = &nul;
}
void upd(node *&p) {
    p->sz = p->ch[0]->sz + p->ch[1]->sz + p->cnt;
    p->jd = p->ls->jd + p->rs->jd + 1;
    p->fjd = p->ls->fjd + p->rs->fjd + (p->cnt?1:0);
}
node *nwnode(int dat) {
    node* p = lj?pool[lj--]:&z[++tot];
    p->ls = p->rs = nul; p->jd = p->fjd = p->sz = p->cnt = 1;
    p->dat = dat;
    return p;
}
int sta[maxn],stac[maxn],top;
bool isbad(node *&p) {
    return (p->ls->fjd*4 > p->fjd*3 || p->rs->fjd*4 > p->fjd*3 || p->fjd*4 < p->jd*3 );
}
void tra(node *&p) {
    if(p==nul) return;
    tra(p->ls);
    pool[++lj] = p;
    if(p->cnt) {
        sta[++top] = p->dat;
        stac[top] = p->cnt;
    }
    tra(p->rs);
}
void build(node *&p,int l,int r) {
    int mid = (l+r)>>1;
    p = nwnode(sta[mid]);
    p->cnt = stac[mid];
    if(l<mid) build(p->ls,l,mid-1);
    if(mid<r) build(p->rs,mid+1,r);
    upd(p);
}
void rebuild() {
    if(*rbrt==nul) return;
    top = 0;
    tra(*rbrt);
    if(top>0) build(*rbrt,1,top);
    else *rbrt = nul;
    rbrt = &nul;
}
void ins(node *&p,int vl) {
    if(p==nul){
        p = nwnode(vl); return;
    }
    if(p->dat == vl) {
        p->cnt++;
        upd(p);
        return;
    } else if(p->dat < vl) ins(p->rs,vl);
    else ins(p->ls,vl);
    upd(p);
    if(isbad(p)) rbrt = &p;
}
void del(node *&p,int vl) {
    if(p == nul) return;
    if(p->dat == vl) p->cnt--;
    else if(p->dat < vl) del(p->rs,vl);
    else del(p->ls,vl);
    upd(p);
    if(isbad(p)) rbrt = &p;
}
int get_little_num(node *&p,int vl) {
    if(p == nul) return 0;
    if(p->dat == vl) return p->ls->sz;
    else if(vl > p->dat) return p->ls->sz+p->cnt+get_little_num(p->rs,vl);
    else return get_little_num(p->ls,vl);
}
int get_kth_num(node *&p,int k) {
    if(p==nul) return 0;
    if(p->cnt && p->ls->sz+1 <= k && k <= p->ls->sz+p->cnt ) return p->dat;
    if(p->ls->sz >= k) return get_kth_num(p->ls,k);
    else return get_kth_num(p->rs,k - p->ls->sz - p->cnt);
}
int getqq(int vl) {
    return get_kth_num(RT,get_little_num(RT,vl));
}
int gethj(int vl) {
    return get_kth_num(RT,get_little_num(RT,vl+1)+1);
}
int main(){
    scanf("%d",&n);
    init();
    int opt,x,k;
    for(int i=1;i<=n;i++) {
        scanf("%d%d",&opt,&x);
        switch(opt) {
            case 1:
                ins(RT,x);
                break;
            case 2:
                del(RT,x);
                break;
            case 3:
                k = get_little_num(RT,x);
                printf("%d\n",k+1);
                break;
            case 4: 
                printf("%d\n",get_kth_num(RT,x)); 
                break; 
            case 5: 
                printf("%d\n",getqq(x)); break;
            case 6: 
                printf("%d\n",gethj(x)); break;
        }
        rebuild();
    }
    return 0;
}

splay模板：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define zig(x) zigzag(x,1)
#define zag(x) zigzag(x,2)
using namespace std;
const int maxn = 200005;
int n,tot,rt;
int alls;
struct node
{
    int ls,rs,dat,pri,fa,cc,siz;
}Z[maxn];
void putup(int x)
{ Z[x].siz=Z[x].cc+Z[Z[x].ls].siz+Z[Z[x].rs].siz; }
void putupall(int x)
{
    putup(x); 
    if(Z[x].fa) putupall(Z[x].fa); 
}
int LJ[maxn],ljt;
int getnew()
{
    int p ;
    if(ljt) p = LJ[ljt--];
    p = ++tot;
    Z[p].ls = Z[p].rs = Z[p].pri = Z[p].dat = Z[p].fa = Z[p].cc = Z[p].siz = 0;
    return p;
}
void zigzag(int x,int knd)
{
    int y=Z[x].fa,z=Z[y].fa;
    if(z)
    {
        if(Z[z].ls==y) Z[z].ls = x;
        else Z[z].rs = x; 
    }
    Z[x].fa = z; Z[y].fa = x;
    if(knd==1)
    {
        Z[y].ls = Z[x].rs;
        Z[Z[y].ls].fa = y;
        Z[x].rs = y;
    }
    else
    {
        Z[y].rs = Z[x].ls;
        Z[Z[y].rs].fa = y;
        Z[x].ls = y;
    }
    if(!Z[x].fa) rt = x;
    putup(y); putup(x);
}
void ins(int key)
{
    ++alls;
    if(!rt)
    {
        rt = getnew();
        Z[rt].dat = key; Z[rt].pri = rand();
        Z[rt].ls = Z[rt].rs = Z[rt].fa = 0;
        Z[rt].siz = Z[rt].cc = 1;
        return;
    }
    int now = rt,p;
    while(now)
    {
        if(Z[now].dat==key)
        {
            Z[now].cc++;
            Z[now].siz++;
            putupall(now);
            return;
        }
        else if(Z[now].dat<key)
        {
            if(Z[now].rs)now = Z[now].rs;
            else
            {
                p = getnew();
                Z[now].rs = p;
                break;
            }
        }
        else
        {
            if(Z[now].ls)now = Z[now].ls;
            else
            {
                p = getnew();
                Z[now].ls = p;
                break;
            }
        }
    }
    Z[p].dat = key; Z[p].siz=Z[p].cc=1; Z[p].ls = Z[p].rs = 0 ;
    Z[p].fa = now; Z[p].pri = rand();
    putupall(p);
    while(Z[p].pri<Z[Z[p].fa].pri)
    {
        if(Z[Z[p].fa].ls==p) zig(p);
        else zag(p);
    }
}
int fi(int key)
{
    int p = rt;
    while(p)
    {
        if(Z[p].dat==key) return p;
        if(Z[p].dat<key) p = Z[p].rs;
        else p = Z[p].ls;
    }
    return 0;
}
int getmin(int p)
{
    while(Z[p].ls) p = Z[p].ls;
    return p;
}
int getmax(int p)
{
    while(Z[p].rs) p = Z[p].rs;
    return p;
}
void del(int key)
{
    --alls;
    if(!alls) rt = 0; 
    int p = fi(key);
    if(!p) return;
    if(Z[p].cc>1)
    {
        --Z[p].cc; --Z[p].siz; 
        putupall(p);
        return;
    }
    while(Z[p].ls||Z[p].rs)
    {
        if(!Z[p].ls) { zag(Z[p].rs); continue; }
        if(!Z[p].rs) { zig(Z[p].ls); continue; }
        if(Z[Z[p].ls].pri<Z[Z[p].rs].pri) zig(Z[p].ls);
        else zag(Z[p].rs);
    }
    putup(p);
    if(Z[p].fa)
    {
    if(p==Z[Z[p].fa].ls) Z[Z[p].fa].ls = 0;
    else Z[Z[p].fa].rs = 0;
    putupall(Z[p].fa);
    }
    LJ[++ljt] = p; 
}
int getk(int k)
{
    int p = rt;
    while(k)
    {
        if(Z[Z[p].ls].siz>=k) p = Z[p].ls;
        else if(Z[Z[p].ls].siz+Z[p].cc<k) k-=Z[Z[p].ls].siz+Z[p].cc,p = Z[p].rs;
        else return p;
    }
    return 0;
}
int getpaiming(int key)
{
    int p = fi(key);
    if(p==rt) return Z[Z[p].ls].siz+1;
    int now = rt;
    int kk = 0;
    while(now)
    {
        if(now==p) { kk+=Z[Z[now].ls].siz; break; };
        if(Z[now].dat<key)
        {
            kk += Z[Z[now].ls].siz + Z[now].cc ; now = Z[now].rs;
        }
        else now = Z[now].ls;
    }
    return kk+1;
}
int getqianqu(int key)
{
    int p = rt; int ans = -0x3f3f3f3f;
    while(p)
    {
        if(Z[p].dat>=key) p = Z[p].ls;
        else
        {
            if(Z[p].dat>ans) ans = Z[p].dat;
            p = Z[p].rs;
        }
    }
    return ans;
}
int gethouji(int key)
{
    int p = rt; int ans = 0x3f3f3f3f;
    while(p)
    {
        if(Z[p].dat<=key) p = Z[p].rs;
        else 
        {
            if(Z[p].dat<ans) ans = Z[p].dat;
            p = Z[p].ls;
        }
    }
    return ans;
}
int main()
{
//  freopen("aha.out","w",stdout);
    srand(19360924);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1) ins(x);
        else if(opt==2) del(x);
        else if(opt==3) printf("%d\n",getpaiming(x));
        else if(opt==4) printf("%d\n",Z[getk(x)].dat);
        else if(opt==5) printf("%d\n",getqianqu(x));
        else printf("%d\n",gethouji(x));
    }
}

vector伪平衡树

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

vector<int>ve;

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int opt,x; scanf("%d%d",&opt,&x);
             if(opt==1) ve.insert(lower_bound(ve.begin(),ve.end(),x),x);
        else if(opt==2) ve.erase(lower_bound(ve.begin(),ve.end(),x));
        else if(opt==3) printf("%d\n",lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1);
        else if(opt==4) printf("%d\n",ve[x-1]);
        else if(opt==5) printf("%d\n",*--lower_bound(ve.begin(),ve.end(),x));
        else if(opt==6) printf("%d\n",*upper_bound(ve.begin(),ve.end(),x));
    }
}

码农公寓

相关文章