B+ Tree

B佳树?圣佳树!

本来以为会比红黑树稍好写一点，实际写了红黑树两倍码量的石山代码

这里只放不同版本的代码, 分析可以见 Blog

注意

除了标记对勾的绿色代码, 其他代码只是为了展示本人赤石的过程, 附带一些分析, 可能会造成混淆

一份错误代码, 锻炼石山纠错能力

#include<bits/stdc++.h>
using namespace std;
const int Null=0, N=2e6+10, M=20, m=(M-1)/2, INF=1e8+10;
int n,o,tot,top;
int a[N],b[N],c[N],stk[N],skt[N]; 
enum type{INTERNAL, LEAF};
#define __B_PLUS_TREE_DEBUG__ 
#define __RED_BLACK_TREE_DEBUG__ 

template<typename T> class B_plus_tree{
    public:
        //enum type{INTERNAL,LEAF};
        struct node{
            int fa,son[M+2],nxt,pre;
            T val[M+2];
            int cnt, id, sz;//cnt: num of val; <=M-1, when >=M, split
            type t;
        };
        node a[N];  
    public:
        int num,rt;
        void Init();
        int build(type t,int fa);
        void insert_val(int u, int s, T val);
        void delete_val(int u, T val);
        void delete_nxt_val(int u, T val);
        void Insert(int u, T val);
        void Delete(int u, T val);
        void split(int u);
        void pushup(int u);
        void merge(int u, int v);
        void change_parent(int u,T pre,T now);
        void fix(int u,T val,int i);
        int getrank(int x, T val);
        T getval(int x, int rank);
        int getpre(int x, T val);
        int getnxt(int x, T val);
        int get_leaf_pre(int u, int id);
        int get_leaf_nxt(int u, int id);
        #ifdef __B_PLUS_TREE_DEBUG__ 
            void dfs(int x){
                assert(x!=0);
                cout<<x<<"(type="<<(a[x].t==LEAF?"LEAF":"INTERNAL");
                cout<<",id="<<a[x].id<<",fa="<<a[x].fa<<",sz="<<a[x].sz;
                if(a[x].t==LEAF) cout<<",nxt="<<a[x].nxt<<",pre="<<a[x].pre;
                cout<<")->[";
                for(int i=0;i<a[x].cnt;++i) cout<<a[x].val[i]<<" ";
                cout<<"]";
                if(a[x].t==INTERNAL){
                    cout<<"{";
                    for(int i=0;i<=a[x].cnt;++i) cout<<a[x].son[i]<<" ";
                    cout<<"}";
                }
                cout<<endl;
                if(a[x].t==LEAF) return;
                for(int i=0;i<a[x].cnt+1;++i) dfs(a[x].son[i]);
            }
            void Dfs(int x){
                assert(x!=0);
                if(a[x].t==LEAF){
                    for(int i=0;i<a[x].cnt;++i) stk[++top]=a[x].val[i];
                    return; 
                }
                for(int i=0;i<a[x].cnt+1;++i){
                    Dfs(a[x].son[i]);
                }
            }
        #endif
};
template<typename T> void B_plus_tree<T>::Init(){
    rt=num=0;
}
template<typename T> void B_plus_tree<T>::pushup(int u){
    if(a[u].t==LEAF) a[u].sz=a[u].cnt;
    else{
        a[u].sz=0;
        for(int i=0;i<=a[u].cnt;++i) a[u].sz+=a[a[u].son[i]].sz,a[a[u].son[i]].id=i,a[a[u].son[i]].fa=u;
    }
}


template<typename T> int B_plus_tree<T>::build(type t,int fa){
    a[++num].t=t;
    a[num].cnt=0;
    a[num].fa=fa;
    return num;
}
template<typename T> int B_plus_tree<T>::get_leaf_nxt(int u, int id){
    if(id<a[u].cnt-1) return a[u].val[id+1];
    else if(a[u].nxt) return a[a[u].nxt].val[0];
    else return INF;
}
template<typename T> int B_plus_tree<T>::get_leaf_pre(int u, int id){
    if(id>0) return a[u].val[id-1];
    else if(a[u].pre) return a[a[u].pre].val[a[a[u].pre].cnt-1];
    else return -INF;
}
template<typename T> void B_plus_tree<T>::insert_val(int u, int s, T val){
    int i=0;
    for(;i<a[u].cnt;++i){
        if(val<a[u].val[i]) break;
        else if(a[u].t==LEAF && val<=a[u].val[i]) break;
    }
    for(int j=a[u].cnt;j>=i+1;--j) a[u].val[j]=a[u].val[j-1],a[u].son[j+1]=a[u].son[j],a[a[u].son[j+1]].id=j+1;
    a[u].val[i]=val,a[u].son[i+1]=s,a[s].id=i+1,a[s].fa=u;
    ++a[u].cnt;
    pushup(u);
}
template<typename T> void B_plus_tree<T>::delete_val(int u, T val){//val i and son i+1
    int i=0;
    for(;i<a[u].cnt;++i) if(val==a[u].val[i]) break;// notice only == ,then delete
    for(int j=i+1;j<=a[u].cnt;++j){
        a[u].val[j-1]=a[u].val[j];
        a[u].son[j]=a[u].son[j+1];
        a[a[u].son[j]].id=j;
    }
    if(i<a[u].cnt) --a[u].cnt;
    pushup(u);
}
template<typename T> void B_plus_tree<T>::delete_nxt_val(int u, T val){//val i and son i
    int i=0;
    for(;i<a[u].cnt;++i) if(val==a[u].val[i]) break;// notice only == ,then delete
    for(int j=i+1;j<=a[u].cnt;++j){
        a[u].val[j-1]=a[u].val[j];
        a[u].son[j-1]=a[u].son[j];
        a[a[u].son[j-1]].id=j-1;
    }
    if(i<a[u].cnt) --a[u].cnt;
    pushup(u);
}

template<typename T> void B_plus_tree<T>::split(int u){
    int mid=(a[u].t==LEAF)?M/2:(M-1)/2,fa=a[u].fa;
    if(!fa) rt=fa=build(INTERNAL,0),a[fa].son[0]=u,a[u].fa=fa,a[u].id=0;
    int v=build(a[u].t, fa);
    insert_val(fa, v, a[u].val[mid]);
    if(a[u].t==LEAF){
        for(int i=mid;i<a[u].cnt;++i) a[v].val[i-mid]=a[u].val[i];
        a[u].cnt=mid,a[v].cnt=M-mid;
        int nxt=a[u].nxt;
        a[v].nxt=nxt,a[u].nxt=v;
        a[nxt].pre=v,a[v].pre=u;
    }else{
        for(int i=mid+1;i<=a[u].cnt;++i){
            if(i<a[u].cnt) a[v].val[i-mid-1]=a[u].val[i];
            a[v].son[i-mid-1]=a[u].son[i];
            a[a[u].son[i]].fa=v;
            a[a[u].son[i]].id=i-mid-1;
        }
        a[u].cnt=mid,a[v].cnt=M-mid-1;
    }
    pushup(u),pushup(v),pushup(fa);
}

template<typename T> void B_plus_tree<T>::Insert(int u, T val){
    if(!rt){
        rt=build(LEAF, 0);
        insert_val(rt, 0, val);
        return;
    }
    int i=0;
    for(;i<a[u].cnt;++i){
        if(val<a[u].val[i]) break;
        else if(a[u].t==LEAF && val<=a[u].val[i]) break;
    }
    if(a[u].t==INTERNAL){
        Insert(a[u].son[i], val);
        if(a[u].cnt>=M) split(u);
    }else{
        insert_val(u, 0, val);
        if(a[u].cnt>=M) split(u);
    }
    pushup(u);
}
template<typename T> void B_plus_tree<T>::change_parent(int u, T pre, T now){
    u=a[u].fa;
    while(u){//INTERNAL
        for(int i=0;i<a[u].cnt;++i){
            if(a[u].val[i]==pre){
                a[u].val[i]=now;
                return;
            }
        }     
        u=a[u].fa;       
    }   
}
template<typename T> void B_plus_tree<T>::merge(int u,int v){
    int fa=a[u].fa,id=a[u].id,val=a[fa].val[id];
    delete_val(fa, val);
    if(a[u].t==LEAF){
        for(int i=0;i<a[v].cnt;++i) a[u].val[a[u].cnt++]=a[v].val[i];
        a[v].cnt=0;
        int nxt=a[v].nxt;
        a[u].nxt=nxt,a[v].nxt=0;
        a[nxt].pre=u,a[v].pre=0;
    }else{
        insert_val(u,a[v].son[0],val);
        for(int i=0;i<a[v].cnt;++i){
            a[u].val[a[u].cnt++]=a[v].val[i];
            a[u].son[a[u].cnt]=a[v].son[i+1];
            a[a[v].son[i+1]].fa=u;
            a[a[v].son[i+1]].id=a[u].cnt;
        }
        a[v].cnt=0;
    }
    pushup(u),pushup(fa);
}
template<typename T> void B_plus_tree<T>::fix(int u, T val, int i){

    int fa=a[u].fa,id=a[u].id;
    if(!fa) return;
    if(a[u].t==LEAF){
        if(id>0 && a[a[fa].son[id-1]].cnt>m){ // borrow pre
            int v=a[fa].son[id-1];
            T pre = a[v].val[a[v].cnt-1];
            if(i==0) change_parent(u, val, pre);
            else change_parent(u, a[u].val[0], pre);
            insert_val(u, 0, pre);//insert me
            a[v].cnt--;//delete pre sibling
            pushup(u),pushup(v);
        }else if(id<a[fa].cnt && a[a[fa].son[id+1]].cnt>m){ // borrow nxt
            int v=a[fa].son[id+1];
            T nxt=0;
            if(i>=a[u].cnt){
                if(a[u].nxt) nxt=a[a[u].nxt].val[0];
                else nxt=INF;
            }else nxt = a[u].val[i];
            if(i==0) change_parent(u, val, nxt);
            nxt = a[v].val[0];
            delete_val(v,nxt);//delete nxt sibling
            insert_val(u,0,nxt);//insert me 
            change_parent(v,nxt,a[v].val[0]);
            pushup(u),pushup(v);
        }else{
            if(i==0) change_parent(u, val, a[u].val[0]); // always change parent when i==0 and LEAF
            if(id>0) merge(a[fa].son[id-1],u);
            else merge(u,a[fa].son[id+1]);    
        }
    }else{
        if(id>0 && a[a[fa].son[id-1]].cnt>m){ // borrow pre
            int v=a[fa].son[id-1],s=a[v].son[a[v].cnt];
            T pre = a[fa].val[id-1];
            a[fa].val[id-1]=a[v].val[a[v].cnt-1];//change fa
            /*insert me*/
            for(int j=a[u].cnt;j>=0;--j){
                if(j>=1) a[u].val[j]=a[u].val[j-1];
                a[u].son[j+1]=a[u].son[j],a[a[u].son[j+1]].id=j+1;
                }
            a[u].val[0]=pre,a[u].son[0]=s,a[s].id=0,a[s].fa=u;
            ++a[u].cnt;
            pushup(u);
            /*insert_nxt_val?*/
            delete_val(v,a[v].val[a[v].cnt-1]);//delete nxt sibling
            pushup(u),pushup(v);
        }else if(id<a[u].cnt && a[a[fa].son[id+1]].cnt>m){ // borrow nxt
            int v=a[fa].son[id+1],s=a[v].son[0];
            T nxt = a[fa].val[id];
            a[fa].val[id]=a[v].val[0];//change fa
            insert_val(u,s,nxt);//insert me 
            delete_nxt_val(v,a[v].val[0]);//delete nxt sibling
            pushup(u),pushup(v);
        }else{  // merge
            if(id>0) merge(a[fa].son[id-1],u);
            else merge(u,a[fa].son[id+1]);    
        }
    }
}
template<typename T> void B_plus_tree<T>::Delete(int u, T val){
    int i=0;
    for(;i<a[u].cnt;++i){
        if(val<a[u].val[i]) break;
        else if(a[u].t==LEAF && val<=a[u].val[i]) break;
    }
    if(a[u].t==INTERNAL){
        Delete(a[u].son[i], val);
        if(u==rt){
            if(a[u].cnt<1){
                rt=a[u].son[0],a[u].fa=0,a[u].t=LEAF;
                pushup(rt);
                return;
            }
        }else{
            if(a[u].cnt<m) fix(u, val, i);
        }
    }else{
        if(a[u].val[i]!=val) return;
        delete_val(u, val);
        if(u==rt && !a[u].cnt){
            rt=0;
            return;
        }
        if(a[u].cnt<m) fix(u, val, i);
        else if(i==0) change_parent(u, val ,a[u].val[0]);
    }
    pushup(u);
}
template<typename T> int B_plus_tree<T>::getrank(int u, T val){
    int t=0;
    for(;t<a[u].cnt;++t){
        if(val<a[u].val[t]) break;
        else if(a[u].t==LEAF && val<=a[u].val[t]) break;
    }
    if(a[u].t==INTERNAL){
        int rank=0;
        for(int j=0;j<t;++j) rank+=a[a[u].son[j]].sz;
        return rank+getrank(a[u].son[t], val);
    }else{
        if(t==0){// may have same value in pre node
            int r=1;
            while(a[u].val[t]==val){
                if(t==0){
                    if(!a[u].pre) return r;
                    else u=a[u].pre,t=a[u].cnt-1;
                }else --t;
                --r;
            }
            ++r;
            return r;
        }else if(t<a[u].cnt){
            return t+1;
        }else{
            int v=a[u].nxt;
            if(v) return a[u].cnt+1;
            else return INF;
        }
    }
}
template<typename T> T B_plus_tree<T>::getval(int u, int rank){
    int i=0;
    if(a[u].t==INTERNAL){
        for(;i<=a[u].cnt;++i){
            if(rank<=a[a[u].son[i]].sz) break; 
            else rank-=a[a[u].son[i]].sz;
        }
        return getval(a[u].son[i], rank);
    }else{
        return a[u].val[rank-1];
    }
}

template<typename T> int B_plus_tree<T>::getpre(int u, T val){
    int i=0;
    for(;i<a[u].cnt;++i){
        if(val<a[u].val[i]) break;
        else if(a[u].t==LEAF && val<=a[u].val[i]) break;
    }
    if(a[u].t==INTERNAL){
        return getpre(a[u].son[i], val);
    }else{
        if(i>=a[u].cnt) return a[u].val[a[u].cnt-1];
        while(a[u].val[i]>=val){

            if(i==0){
                if(!a[u].pre) return -INF;
                else u=a[u].pre,i=a[u].cnt-1;
            }else --i;
        }
        return a[u].val[i];
    }
}
template<typename T> int B_plus_tree<T>::getnxt(int u, T val){
    int i=0;
    for(;i<a[u].cnt;++i){
        if(val<a[u].val[i]) break;
    }
    if(a[u].t==INTERNAL){
        return getnxt(a[u].son[i], val);
    }else{
        if(i<a[u].cnt){
            return a[u].val[i];
        }else{
            int v=a[u].nxt;
            if(v && a[v].val[0]>val/*not necessary*/) return a[v].val[0];
            else return INF;
        }
    }
}
B_plus_tree<int> S;
void solve() {
    scanf("%d",&n);
    S.Init();
    tot=0;
    for(o=1;o<=n;++o){
        int op,x; 
        scanf("%d%d",&op,&x);
        if(op>=3) c[++tot]=o;
        if(op==1){
            S.Insert(S.rt, x);
        }else if(op==2){
            S.Delete(S.rt, x);   
        }else if(op==3){
            printf("%d\n",S.getrank(S.rt, x));
        }else if(op==4){
            printf("%d\n",S.getval(S.rt, x));
        }else if(op==5){
            printf("%d\n",S.getpre(S.rt, x));
        }else if(op==6){
            printf("%d\n",S.getnxt(S.rt, x));
        }
    }
}
int main() {
    solve(); 
    return 0;
}

你会发现 \(M=20\) 可过 P3369, 但更小的 \(M\) 就可能过不了

主要问题

0x00. 重复的键值

数据不保证不出现重复的值, 而我喜欢赤石, 我写的带重复的B+树

在change_parent, getpre, getnxt, getrank中都需要特判是否有重复的值，才能得到正确答案

例如，change_parent 中，如果我们要改的pre有很多个，那么就需要判断now的大小，如果小于pre就要加到第一个pre之前，否则要加到最后一个pre之后

这份代码有一些函数已经注意到了这个问题，另一些还没改

0x01. 瞎pushup

这份代码删除节点后节点没有消失(又是数组的原因，不长记性了，为什么不用指针呢？)

并且也没有进行解绑

这意味着在 merge(x,y) 时，y 被删除，而如果 Delete(u) 递归的是u=y,你看到函数最后的pushup(u)了吗？这会导致y的儿子的fa指针重新指向y, 导致出错

所以，直接去掉pushup中对于fa的维护，并进行解绑

由于之前的某些错误，fa维护错误，所以这份代码暴力地加上了pushup对fa的维护，结果这导致了新的错误

事实上，这份代码的id是存起来的，这个操作也导致了某些错误，后面直接去掉了id, 改为直接暴力查询

0x02. 插入/删除的方向

在fix函数中，我们的borrow_pre和borrow_nxt中调用了insert_val和delete_val, 而这两个函数是插入/删除第i个键值和第i+1个儿子

但是，borrow_nxt 的\(nxt\)节点删除儿子是删除第\(0\)个键值和第\(0\)个儿子

borrow_pre 的自己插入儿子是插入第\(0\)个键值和第\(0\)个儿子

所以要写\(4\)个不同的函数来插入/删除：

insert_left_by_id, insert_right_by_id, delete_left_by_id, delete_right_by_id

0x03. change_parent

还是这破玩意

在 Delete 到叶子节点，如果没有出现节点过少，不能直接结束，而要判断删的是不是第0个数，如果是要进行替换

这份代码注意到了这个问题

在 borrow_nxt 中同样有，如果删的是不是第0个数，要进行替换

这份代码没有注意到这个问题

上一个都注意到了，后一个却忽略了，注意力太不集中了

有重复B+树

注意 change_parent 函数 (单次\(O(M\log_MN)\)) 不会让最坏复杂度变成 \(O(M\log_M^2 N)\), 因为只有叶子节点会调用 change_parent, 所以一次操作只会做常数次 change_parent, 复杂度仍为 \(O(M\log_MN)\)

具体来说, 一次操作最多出现 \(3\) 次 change_parent, 例如 borrow_nxt 情况的删除, 要删除 x, 先将叶子节点删空, 将内部节点的 x 改成 NULL;

再从兄弟节点借一个节点过来, 兄弟节点的新 val[0] 再进行一次 change_parent

最后兄弟节点借来的值 y 将 NULL 替换掉

一共 \(3\) 次 change_parent

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10, INF=1e8+10;
int n,o,tot,top,pot;
int a[N],b[N],c[N],stk[N],skt[N]; 
#define __B_PLUS_TREE_DEBUG__ 

template<typename T> class B_plus_tree {
    public:
        static const int  M=5, m=(M-1)/2;
        enum type{INTERNAL,LEAF};
        struct node {
            int fa,son[M+2],nxt,pre;
            T val[M+2];
            int cnt, sz;//cnt: num of val; <=M-1, when >=M, split
            type t;
        };
        node a[N];
    public:
        int num,rt;
        void Init();
        int build(type t,int fa);
        void insert_val(int u, int s, T val);
        void delete_val(int u, T val);
        void insert_left_by_id(int u, int id, int s, T val);
        void insert_right_by_id(int u, int id, int s, T val);
        void delete_left_by_id(int u, int id);
        void delete_right_by_id(int u, int id);
        void Insert(int u, T val);
        void Delete(int u, T val);
        void split(int u);
        void pushup(int u);
        void merge(int u, int v);
        void change_parent(int u,T pre,T now);
        void fix(int u,T val,int i);
        int getrank(int x, T val);
        T getval(int x, int rank);
        int getpre(int x, T val);
        int getnxt(int x, T val);
        int get_id(int u);
#ifdef __B_PLUS_TREE_DEBUG__
        void dfs(int x) {
            assert(x!=0);
            cout<<x<<"(type="<<(a[x].t==LEAF?"LEAF":"INTERNAL");
            cout<<",id="<<get_id(x)<<",fa="<<a[x].fa<<",sz="<<a[x].sz;
            if(a[x].t==LEAF) cout<<",nxt="<<a[x].nxt<<",pre="<<a[x].pre;
            cout<<")->[";
            for(int i=0; i<a[x].cnt; ++i) cout<<a[x].val[i]<<" ";
            cout<<"]";
            if(a[x].t==INTERNAL) {
                cout<<"{";
                for(int i=0; i<=a[x].cnt; ++i) cout<<a[x].son[i]<<" ";
                cout<<"}";
            }
            cout<<endl;
            if(a[x].t==LEAF) return;
            for(int i=0; i<a[x].cnt+1; ++i) dfs(a[x].son[i]);
        }
        void Dfs(int x) {
            assert(x!=0);
            if(a[x].t==LEAF) {
                for(int i=0; i<a[x].cnt; ++i) stk[++top]=a[x].val[i];
                return;
            }

            for(int i=0; i<a[x].cnt+1; ++i) {
                Dfs(a[x].son[i]);
            }

        }
#endif
};
template<typename T> void B_plus_tree<T>::Init() {
    rt=num=0;
}
template<typename T> int B_plus_tree<T>::get_id(int u) {
    int fa=a[u].fa;
    for(int i=0; i<=a[fa].cnt; ++i) {
        if(a[fa].son[i]==u) return i;
    }
}
template<typename T> void B_plus_tree<T>::pushup(int u) {
    if(a[u].t==LEAF) a[u].sz=a[u].cnt;
    else {
        a[u].sz=0;
        for(int i=0; i<=a[u].cnt; ++i) a[u].sz+=a[a[u].son[i]].sz,a[a[u].son[i]].fa=u;
    }
}
template<typename T> int B_plus_tree<T>::build(type t,int fa) {
    a[++num].t=t;
    a[num].cnt=0;
    a[num].fa=fa;
    return num;
}
template<typename T> void B_plus_tree<T>::insert_val(int u, int s, T val) {

    int i=0;
    for(; i<a[u].cnt; ++i) {
        if(val<a[u].val[i]) break;
        else if(a[u].t==LEAF && val<=a[u].val[i]) break;
    }
    for(int j=a[u].cnt; j>=i+1; --j) a[u].val[j]=a[u].val[j-1],a[u].son[j+1]=a[u].son[j];
    a[u].val[i]=val,a[u].son[i+1]=s,a[s].fa=u;
    ++a[u].cnt;
    pushup(u);
}
template<typename T> void B_plus_tree<T>::delete_val(int u, T val) { //val i and son i+1
    int i=0;
    for(; i<a[u].cnt; ++i) if(val==a[u].val[i]) break; // notice only == ,then delete
    if(i>=a[u].cnt) return;
    a[a[u].son[i+1]].fa=0;
    for(int j=i+1; j<a[u].cnt; ++j) {
        a[u].val[j-1]=a[u].val[j];
        a[u].son[j]=a[u].son[j+1];
    }
    a[u].val[a[u].cnt-1]=0,a[u].son[a[u].cnt]=0,--a[u].cnt;
    pushup(u);
}
template<typename T> void B_plus_tree<T>::insert_left_by_id(int u, int id, int s, T val) {//insert val id and son id
    for(int i=a[u].cnt;i>=id;--i){ // id>=0
        if(i>=1) a[u].val[i]=a[u].val[i-1];
        a[u].son[i+1]=a[u].son[i];
    }
    a[u].val[id]=val;
    if(a[u].t==INTERNAL) a[u].son[id]=s,a[s].fa=u;
    ++a[u].cnt;
    pushup(u);
}
template<typename T> void B_plus_tree<T>::insert_right_by_id(int u, int id, int s, T val) {//insert val id and son id+1
    for(int i=a[u].cnt;i>=id+1;--i){ // id>=0
        a[u].val[i]=a[u].val[i-1];
        a[u].son[i+1]=a[u].son[i];
    }
    a[u].val[id]=val;
    if(a[u].t==INTERNAL) a[u].son[id+1]=s,a[s].fa=u;
    ++a[u].cnt;
    pushup(u);
}
template<typename T> void B_plus_tree<T>::delete_left_by_id(int u, int id) {//delete val id and son id
    for(int i=id+1;i<=a[u].cnt;++i){
        if(i<a[u].cnt) a[u].val[i-1]=a[u].val[i];
        a[u].son[i-1]=a[u].son[i];
    } 
    a[u].son[a[u].cnt]=0,a[u].val[a[u].cnt-1]=0;
    a[u].cnt--;
    pushup(u);
} 
template<typename T> void B_plus_tree<T>::delete_right_by_id(int u, int id) {//delete val id and son id+1

    for(int i=id+1;i<a[u].cnt;++i){
        a[u].val[i-1]=a[u].val[i];
        a[u].son[i]=a[u].son[i+1];
    }
    a[u].val[a[u].cnt-1]=0,a[u].son[a[u].cnt]=0;
    a[u].cnt--;
    pushup(u);
}
template<typename T> void B_plus_tree<T>::split(int u) {
    int mid=(a[u].t==LEAF)?M/2:(M-1)/2,fa=a[u].fa;
    if(!fa) rt=fa=build(INTERNAL,0),a[fa].son[0]=u,a[u].fa=fa;
    int v=build(a[u].t, fa),id=get_id(u);
    insert_right_by_id(fa, id, v, a[u].val[mid]); 
    if(a[u].t==LEAF) {
        for(int i=mid; i<a[u].cnt; ++i) a[v].val[i-mid]=a[u].val[i],a[u].val[i]=0;
        a[u].cnt=mid,a[v].cnt=M-mid;
        int nxt=a[u].nxt;
        a[v].nxt=nxt,a[u].nxt=v;
        a[nxt].pre=v,a[v].pre=u;
    } else {
        for(int i=mid+1; i<=a[u].cnt; ++i) {
            if(i<a[u].cnt) a[v].val[i-mid-1]=a[u].val[i],a[u].val[i]=0;
            a[v].son[i-mid-1]=a[u].son[i];
            a[a[u].son[i]].fa=v;
            a[u].son[i]=0;
        }
        a[u].cnt=mid,a[v].cnt=M-mid-1;
    }
    pushup(u),pushup(v);
    pushup(fa);
}

template<typename T> void B_plus_tree<T>::Insert(int u, T val) {
    if(!rt) {
        rt=build(LEAF, 0);
        insert_val(rt, 0, val);
        pushup(rt);
        return;
    }
    int i=0;
    for(; i<a[u].cnt; ++i) {
        if(val<a[u].val[i]) break;
        else if(a[u].t==LEAF && val<=a[u].val[i]) break;
    }
    if(a[u].t==INTERNAL) {
        Insert(a[u].son[i], val);
        if(a[u].cnt>=M) split(u);
    } else {
        insert_val(u, 0, val);
        if(a[u].cnt>=M) split(u);
    }
    pushup(u);
}
template<typename T> void B_plus_tree<T>::change_parent(int u, T pre, T now) {
    u=a[u].fa;
    if(pre==now) return;
    while(u) { //INTERNAL
        if(pre<now){
            for(int i=a[u].cnt-1; i>=0; --i) {
                if(a[u].val[i]==pre) {
                    a[u].val[i]=now;
                    return;
                }
            }
        }else{
            for(int i=0; i<a[u].cnt; ++i) {
                if(a[u].val[i]==pre) {
                    a[u].val[i]=now;
                    return;
                }
            }
        }
        u=a[u].fa;
    }
}
template<typename T> void B_plus_tree<T>::merge(int u,int v) {
    int fa=a[u].fa,id=get_id(u),val=a[fa].val[id];
    delete_right_by_id(fa, id);
    a[v].fa=0;//
    if(a[u].t==LEAF) {
        for(int i=0; i<a[v].cnt; ++i) a[u].val[a[u].cnt++]=a[v].val[i],a[v].val[i]=0;
        a[v].cnt=0;
        int nxt=a[v].nxt;
        a[u].nxt=nxt,a[v].nxt=0;
        a[nxt].pre=u,a[v].pre=0;
    } else {
        insert_right_by_id(u,a[u].cnt,a[v].son[0],val); 
        for(int i=0; i<a[v].cnt; ++i) {
            a[u].val[a[u].cnt++]=a[v].val[i];
            a[u].son[a[u].cnt]=a[v].son[i+1];
            a[a[v].son[i+1]].fa=u;
            a[v].son[i+1]=a[v].val[i]=0;
        }
        a[v].cnt=0;
    }
    pushup(u);
}
template<typename T> void B_plus_tree<T>::fix(int u, T val, int i) {
    int fa=a[u].fa,id=get_id(u);
    if(!fa) return;
    if(a[u].t==LEAF) {
        if(id>0 && a[a[fa].son[id-1]].cnt>m) { // borrow pre
            int v=a[fa].son[id-1];
            T pre = a[v].val[a[v].cnt-1];
            if(i==0) change_parent(u, val, pre);
            else change_parent(u, a[u].val[0], pre);
            insert_left_by_id(u, 0, 0, pre);
            delete_right_by_id(v, a[v].cnt-1);
            pushup(u),pushup(v);
        } else if(id<a[fa].cnt && a[a[fa].son[id+1]].cnt>m) { // borrow nxt
            int v=a[fa].son[id+1];
            T nxt=0, Nxt=a[v].val[0];
            if(i>=a[u].cnt) {
                if(a[u].nxt) nxt=a[a[u].nxt].val[0];
                else nxt=INF;
            } else nxt = a[u].val[i];
            delete_left_by_id(v,0);
            insert_right_by_id(u,a[u].cnt,0,Nxt);
            change_parent(v, Nxt, a[v].val[0]);
            if(i==0) change_parent(u, val, nxt);
            pushup(u),pushup(v);
        } else {
            if(i==0){
                int nxt = 0; // nxt bigger num than val
                if(a[u].cnt) nxt = a[u].val[0];
                else{
                    if(a[u].nxt) nxt = a[a[u].nxt].val[0];
                    else nxt=INF;
                }
                change_parent(u, val, nxt); // always change parent when i==0 and LEAF
            }
            if(id>0) merge(a[fa].son[id-1],u);
            else merge(u,a[fa].son[id+1]);
        }
    } else {
        if(id>0 && a[a[fa].son[id-1]].cnt>m) { // borrow pre
            int v=a[fa].son[id-1],s=a[v].son[a[v].cnt];
            T pre = a[fa].val[id-1];
            a[fa].val[id-1]=a[v].val[a[v].cnt-1];//change fa
            insert_left_by_id(u,0,s,pre);
            delete_right_by_id(v,a[v].cnt-1);
            pushup(u),pushup(v);
        } else if(id<a[fa].cnt && a[a[fa].son[id+1]].cnt>m) { // borrow nxt
            int v=a[fa].son[id+1],s=a[v].son[0];
            T nxt = a[fa].val[id];
            a[fa].val[id]=a[v].val[0];//change fa
            insert_right_by_id(u,a[u].cnt,s,nxt);
            delete_left_by_id(v,0);
            pushup(u),pushup(v);
        } else { // merge
            if(id>0) merge(a[fa].son[id-1],u);
            else merge(u,a[fa].son[id+1]);
        }
    }
}
template<typename T> void B_plus_tree<T>::Delete(int u, T val) {
    int i=0;
    for(; i<a[u].cnt; ++i) {
        if(val<a[u].val[i]) break;
        else if(a[u].t==LEAF && val<=a[u].val[i]) break;
    }
    if(a[u].t==INTERNAL) {
        Delete(a[u].son[i], val);
        if(u==rt) {
            if(a[u].cnt<1) {
                rt=a[u].son[0],a[rt].fa=0;
                pushup(rt);
                return;
            }
        } else {
            if(a[u].cnt<m) fix(u, val, i);
            else pushup(u);
        }
    } else {
        if(a[u].val[i]!=val) return;
        delete_val(u, val);
        if(u==rt && !a[u].cnt) {
            rt=0;
            return;
        }
        if(a[u].cnt<m) fix(u, val, i);
        else {
            if(i==0) change_parent(u, val ,a[u].val[0]);
            pushup(u);
        }
    }
}
template<typename T> int B_plus_tree<T>::getrank(int u, T val) {
    int t=0;
    for(; t<a[u].cnt; ++t) {
        if(val<a[u].val[t]) break;
        else if(a[u].t==LEAF && val<=a[u].val[t]) break;
    }
    if(a[u].t==INTERNAL) {
        int rank=0;
        for(int j=0; j<t; ++j) rank+=a[a[u].son[j]].sz;
        return rank+getrank(a[u].son[t], val);
    } else {
        if(t==0) { // may have same value in pre node
            int r=1;
            while(a[u].val[t]==val) {
                if(t==0) {
                    if(!a[u].pre) return r;
                    else u=a[u].pre,t=a[u].cnt-1;
                } else --t;
                --r;
            }
            ++r;
            return r;
        } else if(t<a[u].cnt) {
            return t+1;
        } else {
            int v=a[u].nxt;
            if(v) return a[u].cnt+1;
            else return INF;
        }
    }
}
template<typename T> T B_plus_tree<T>::getval(int u, int rank) {
    int i=0;
    if(a[u].t==INTERNAL) {
        for(; i<=a[u].cnt; ++i) {
            if(rank<=a[a[u].son[i]].sz) break;
            else rank-=a[a[u].son[i]].sz;
        }
        return getval(a[u].son[i], rank);
    } else {
        return a[u].val[rank-1];
    }
}

template<typename T> int B_plus_tree<T>::getpre(int u, T val) {
    int i=0;
    for(; i<a[u].cnt; ++i) {
        if(val<a[u].val[i]) break;
        else if(a[u].t==LEAF && val<=a[u].val[i]) break;
    }
    if(a[u].t==INTERNAL) return getpre(a[u].son[i], val);
    else {
        if(i>=a[u].cnt) return a[u].val[a[u].cnt-1];
        while(a[u].val[i]>=val) {
            if(i==0) {
                if(!a[u].pre) return -INF;
                else u=a[u].pre,i=a[u].cnt-1;
            } else --i;
        }
        return a[u].val[i];
    }
}
template<typename T> int B_plus_tree<T>::getnxt(int u, T val) {
    int i=0;
    for(; i<a[u].cnt; ++i) if(val<a[u].val[i]) break;
    if(a[u].t==INTERNAL) return getnxt(a[u].son[i], val);
    else {
        if(i<a[u].cnt) return a[u].val[i];
        else {
            do {
                if(i==a[u].cnt) {
                    if(!a[u].nxt) return INF;
                    else u=a[u].nxt, i=0;
                } else ++i;
            } while(a[u].val[i]<=val);
            return a[u].val[i];
        }
    }
}
B_plus_tree<int> S;
void solve() {
    scanf("%d",&n);
    S.Init();
    for(o=1;o<=n;++o){
        int op,x; 
        scanf("%d%d",&op,&x);
        if(op==1){
            S.Insert(S.rt, x);
        }else if(op==2){
            S.Delete(S.rt, x);   
        }else if(op==3){
            printf("%d\n",S.getrank(S.rt, x));
        }else if(op==4){
            printf("%d\n",S.getval(S.rt, x));
        }else if(op==5){
            printf("%d\n",S.getpre(S.rt, x));
        }else if(op==6){
            printf("%d\n",S.getnxt(S.rt, x));
        }
    }
}
int main() {
    solve(); 
    return 0;
}

P3369: 250ms

无重复B+树

上面写了个带重复节点的B+树，有点难写

去除重复节点，用一个\(cnt\)计数，就会让代码好写一点

#include<bits/stdc++.h>
using namespace std;
const int Null=0, N=2e6+10, INF=1e8+10;
int n,o,tot,top,pot;

#define __B_PLUS_TREE_DEBUG__ 

template<typename T> class B_plus_tree {
private:
    struct Value{
        T value;
        int count;
        Value(T value, int count):value(value),count(count){}
        Value(){}
        bool operator <(const Value &x)const{
            return value<x.value;
        }
    };
    static const int M=3, m=(M-1)/2;
    enum type{INTERNAL,LEAF};
    struct node {
        int fa,son[M+2],nxt,pre;
        Value val[M+2];
        int cnt, sz;//cnt: num of val; <=M-1, when >=M, split
        type t;
    };
    node a[N];
    int build(type t,int fa);
    void insert_left_by_id(int u, int id, int s, Value val);
    void insert_right_by_id(int u, int id, int s, Value val);
    void delete_left_by_id(int u, int id);
    void delete_right_by_id(int u, int id);
    void split(int u);
    void pushup(int u);
    void merge(int u, int v);
    void change_parent(int u,T pre,T now);
    void fix(int u, T val, int i);
    int get_id(int u);
public:
    int num,rt;
    void Init();
    void Insert(int u, T val);
    void Delete(int u, T val);
    int getrank(int x, T val);
    T getval(int x, int rank);
    int getpre(int x, T val);
    int getnxt(int x, T val);
#ifdef __B_PLUS_TREE_DEBUG__
    void dfs(int x) {
        assert(x!=0);
        cout<<x<<"(type="<<(a[x].t==LEAF?"LEAF":"INTERNAL");
        cout<<",id="<<get_id(x)<<",fa="<<a[x].fa<<",sz="<<a[x].sz;
        if(a[x].t==LEAF) cout<<",nxt="<<a[x].nxt<<",pre="<<a[x].pre;
        cout<<")->[";
        for(int i=0; i<a[x].cnt; ++i) cout<<a[x].val[i].value<<" ";
        cout<<"]";
        if(a[x].t==INTERNAL) {
            cout<<"{";
            for(int i=0; i<=a[x].cnt; ++i) cout<<a[x].son[i]<<" ";
            cout<<"}";
        }
        cout<<endl;
        if(a[x].t==LEAF) return;
        for(int i=0; i<a[x].cnt+1; ++i) dfs(a[x].son[i]);
    }
#endif
};
template<typename T> void B_plus_tree<T>::Init() {
    rt=num=0;
}
template<typename T> int B_plus_tree<T>::get_id(int u) {
    int fa=a[u].fa;
    for(int i=0; i<=a[fa].cnt; ++i) {
        if(a[fa].son[i]==u) return i;
    }
}
template<typename T> void B_plus_tree<T>::pushup(int u) {
    if(a[u].t==LEAF){
        a[u].sz=0;
        for(int i=0; i<a[u].cnt; ++i) a[u].sz+=a[u].val[i].count;
    }else {
        a[u].sz=0;
        for(int i=0; i<=a[u].cnt; ++i) a[u].sz+=a[a[u].son[i]].sz;//,a[a[u].son[i]].fa=u;
    }
}
template<typename T> int B_plus_tree<T>::build(type t,int fa) {
    a[++num].t=t;
    a[num].cnt=0;
    a[num].fa=fa;
    return num;
}
template<typename T> void B_plus_tree<T>::insert_left_by_id(int u, int id, int s, Value val) {//insert val id and son id
    for(int i=a[u].cnt;i>=id;--i){ // id>=0
        if(i>=1) a[u].val[i]=a[u].val[i-1];
        a[u].son[i+1]=a[u].son[i];
    }
    a[u].val[id]=val;
    if(a[u].t==INTERNAL) a[u].son[id]=s,a[s].fa=u;
    ++a[u].cnt;
    pushup(u);
}
template<typename T> void B_plus_tree<T>::insert_right_by_id(int u, int id, int s, Value val) {//insert val id and son id+1
    for(int i=a[u].cnt;i>=id+1;--i){ // id>=0
        a[u].val[i]=a[u].val[i-1];
        a[u].son[i+1]=a[u].son[i];
    }
    a[u].val[id]=val;
    if(a[u].t==INTERNAL) a[u].son[id+1]=s,a[s].fa=u;
    ++a[u].cnt;
    pushup(u);
}
template<typename T> void B_plus_tree<T>::delete_left_by_id(int u, int id) {//delete val id and son id
    for(int i=id+1;i<=a[u].cnt;++i){
        if(i<a[u].cnt) a[u].val[i-1]=a[u].val[i];
        a[u].son[i-1]=a[u].son[i];
    } 
    a[u].son[a[u].cnt]=0,a[u].val[a[u].cnt-1]=Value(0, 0);
    a[u].cnt--;
    pushup(u);
} 
template<typename T> void B_plus_tree<T>::delete_right_by_id(int u, int id) {//delete val id and son id+1
    for(int i=id+1;i<a[u].cnt;++i){
        a[u].val[i-1]=a[u].val[i];
        a[u].son[i]=a[u].son[i+1];
    }
    a[u].son[a[u].cnt]=0,a[u].val[a[u].cnt-1]=Value(0, 0);
    a[u].cnt--;
    pushup(u);
}
template<typename T> void B_plus_tree<T>::split(int u) {
    int mid=(a[u].t==LEAF)?M/2:(M-1)/2,fa=a[u].fa;
    if(!fa) rt=fa=build(INTERNAL,0),a[fa].son[0]=u,a[u].fa=fa;
    int v=build(a[u].t, fa),id=get_id(u);
    insert_right_by_id(fa, id, v, a[u].val[mid]); 
    if(a[u].t==LEAF) {
        for(int i=mid; i<a[u].cnt; ++i) a[v].val[i-mid]=a[u].val[i],a[u].val[i]=Value(0, 0);
        a[u].cnt=mid,a[v].cnt=M-mid;
        int nxt=a[u].nxt;
        a[v].nxt=nxt,a[u].nxt=v;
        a[nxt].pre=v,a[v].pre=u;
    } else {
        for(int i=mid+1; i<=a[u].cnt; ++i) {
            if(i<a[u].cnt) a[v].val[i-mid-1]=a[u].val[i],a[u].val[i]=Value(0, 0);
            a[v].son[i-mid-1]=a[u].son[i];
            a[a[u].son[i]].fa=v;
            a[u].son[i]=0;
        }
        a[u].cnt=mid,a[v].cnt=M-mid-1;
    }
    pushup(u),pushup(v);
    pushup(fa);
}

template<typename T> void B_plus_tree<T>::Insert(int u, T val) {
    if(!rt) {
        rt=build(LEAF, 0);
        insert_right_by_id(rt, 0, 0, Value(val, 1));
        pushup(rt);
        return;
    }
    int i=0;
    for(; i<a[u].cnt; ++i) {
        if(val<a[u].val[i].value) break;
        else if(a[u].t==LEAF && val<=a[u].val[i].value) break;
    }
    if(a[u].t==INTERNAL) {
        Insert(a[u].son[i], val);
        if(a[u].cnt>=M) split(u);
    } else {
        if(val == a[u].val[i].value){
            ++a[u].val[i].count;
        }else{
            insert_right_by_id(u, i, 0, Value(val, 1));
            if(a[u].cnt>=M) split(u);
        }
    }
    pushup(u);
}
template<typename T> void B_plus_tree<T>::change_parent(int u, T pre, T now) {
    u=a[u].fa;
    if(pre==now) return;
    while(u) { //INTERNAL
        for(int i=a[u].cnt-1; i>=0; --i) {
            if(a[u].val[i].value==pre) {
                a[u].val[i].value=now;
                return;
            }
        }
        u=a[u].fa;
    }
}
template<typename T> void B_plus_tree<T>::merge(int u,int v) {
    int fa=a[u].fa,id=get_id(u);
    Value val=a[fa].val[id];
    delete_right_by_id(fa, id);
    a[v].fa=0;//
    if(a[u].t==LEAF) {
        for(int i=0; i<a[v].cnt; ++i) a[u].val[a[u].cnt++]=a[v].val[i],a[v].val[i]=Value(0, 0);
        a[v].cnt=0;
        int nxt=a[v].nxt;
        a[u].nxt=nxt,a[v].nxt=0;
        a[nxt].pre=u,a[v].pre=0;
    } else {
        insert_right_by_id(u,a[u].cnt,a[v].son[0],val); 
        for(int i=0; i<a[v].cnt; ++i) {
            a[u].val[a[u].cnt++]=a[v].val[i];
            a[u].son[a[u].cnt]=a[v].son[i+1];
            a[a[v].son[i+1]].fa=u;
            a[v].son[i+1]=0,a[v].val[i]=Value(0, 0);
        }
        a[v].cnt=0;
    }
    pushup(u);
}
template<typename T> void B_plus_tree<T>::fix(int u, T val, int i) {
    int fa=a[u].fa,id=get_id(u);
    if(!fa) return;
    if(a[u].t==LEAF) {
        if(id>0 && a[a[fa].son[id-1]].cnt>m) { // borrow pre
            int v=a[fa].son[id-1];
            Value pre = a[v].val[a[v].cnt-1];
            if(i==0) change_parent(u, val, pre.value);
            else change_parent(u, a[u].val[0].value, pre.value);
            insert_left_by_id(u, 0, 0, pre);
            delete_right_by_id(v, a[v].cnt-1);
            pushup(u),pushup(v);
        } else if(id<a[fa].cnt && a[a[fa].son[id+1]].cnt>m) { // borrow nxt
            int v=a[fa].son[id+1];
            Value nxt=Value(0, 0), Nxt=a[v].val[0];
            if(i>=a[u].cnt) nxt=a[a[u].nxt].val[0];
            else nxt = a[u].val[i];
            delete_left_by_id(v,0);
            insert_right_by_id(u, a[u].cnt, 0, Nxt);
            change_parent(v, Nxt.value, a[v].val[0].value);
            if(i==0) change_parent(u, val, nxt.value);
            pushup(u), pushup(v);
        } else {
            if(i==0){// if merge son[id+1] and i==0, change parent value corresponding to u
                T nxt = 0; // nxt bigger num than val
                if(a[u].cnt) nxt = a[u].val[0].value;
                else nxt = a[a[u].nxt].val[0].value;// no need to make nxt=INF, because if no nxt, it must be merge id-1, then the value will be deleted 
                change_parent(u, val, nxt); // always change parent when i==0 and LEAF
            }
            if(id>0) merge(a[fa].son[id-1],u);
            else merge(u,a[fa].son[id+1]);
        }
    } else {
        if(id>0 && a[a[fa].son[id-1]].cnt>m) { // borrow pre
            int v=a[fa].son[id-1],s=a[v].son[a[v].cnt];
            Value pre = a[fa].val[id-1];
            a[fa].val[id-1]=a[v].val[a[v].cnt-1];//change fa
            insert_left_by_id(u,0,s,pre);
            delete_right_by_id(v,a[v].cnt-1);
            pushup(u),pushup(v);
        } else if(id<a[fa].cnt && a[a[fa].son[id+1]].cnt>m) { // borrow nxt
            int v=a[fa].son[id+1],s=a[v].son[0];
            Value nxt = a[fa].val[id];
            a[fa].val[id]=a[v].val[0];//change fa
            insert_right_by_id(u,a[u].cnt,s,nxt);
            delete_left_by_id(v,0);
            pushup(u),pushup(v);
        } else { // merge
            if(id>0) merge(a[fa].son[id-1],u);
            else merge(u,a[fa].son[id+1]);
        }
    }
}
template<typename T> void B_plus_tree<T>::Delete(int u, T val) {
    int i=0;
    for(; i<a[u].cnt; ++i) {
        if(val<a[u].val[i].value) break;
        else if(a[u].t==LEAF && val<=a[u].val[i].value) break;
    }
    if(a[u].t==INTERNAL) {
        Delete(a[u].son[i], val);
        if(u==rt) {
            if(a[u].cnt<1) {
                rt=a[u].son[0],a[rt].fa=0;
                pushup(rt);
                return;
            }
        } else {
            if(a[u].cnt<m) fix(u, val, i);
            else pushup(u);
        }
    } else {
        if(a[u].val[i].value!=val) return;
        if(a[u].val[i].count>1){
            --a[u].val[i].count;
            pushup(u);
            return;
        }
        delete_right_by_id(u, i);
        if(u==rt && !a[u].cnt) {
            rt=0;
            return;
        }
        if(a[u].cnt<m) fix(u, val, i);
        else {
            if(i==0) change_parent(u, val ,a[u].val[0].value);
            pushup(u);
        }
    }
}
template<typename T> int B_plus_tree<T>::getrank(int u, T val) {
    int t=0;
    for(; t<a[u].cnt; ++t) {
        if(val<a[u].val[t].value) break;
        else if(a[u].t==LEAF && val<=a[u].val[t].value) break;
    }
    if(a[u].t==INTERNAL) {
        int rank=0;
        for(int j=0; j<t; ++j) rank+=a[a[u].son[j]].sz;
        return rank+getrank(a[u].son[t], val);
    } else {
        if(t<a[u].cnt) {
            int res = 0;
            for(int i=0;i<t;++i) res += a[u].val[i].count;
            return res+1;
        } else {
            int v=a[u].nxt;
            if(v) return a[u].sz+1;
            else return INF;
        }
    }
}
template<typename T> T B_plus_tree<T>::getval(int u, int rank) {
    int i=0;
    if(a[u].t==INTERNAL) {
        for(; i<=a[u].cnt; ++i) {
            if(rank<=a[a[u].son[i]].sz) break;
            else rank-=a[a[u].son[i]].sz;
        }
        return getval(a[u].son[i], rank);
    } else {
        for(i=0;i<a[u].cnt;++i){
            if(rank>=1 && rank<=a[u].val[i].count) return a[u].val[i].value;
            else rank-=a[u].val[i].count;
        }
        //return INF;
    }
}

template<typename T> int B_plus_tree<T>::getpre(int u, T val) {
    int i=0;
    for(; i<a[u].cnt; ++i) {
        if(val<a[u].val[i].value) break;
        else if(a[u].t==LEAF && val<=a[u].val[i].value) break;
    }
    if(a[u].t==INTERNAL) return getpre(a[u].son[i], val);
    else {
        if(i==0) {
            if(!a[u].pre) return -INF;
            else u=a[u].pre,i=a[u].cnt;
        }
        return a[u].val[i-1].value;
    }
}
template<typename T> int B_plus_tree<T>::getnxt(int u, T val) {
    int i=0;
    for(; i<a[u].cnt; ++i) if(val<a[u].val[i].value) break;
    if(a[u].t==INTERNAL) return getnxt(a[u].son[i], val);
    else {
        if(i==a[u].cnt){
            if(!a[u].nxt) return INF;
            else u=a[u].nxt, i=0;
        }
        return a[u].val[i].value;
    }
}
B_plus_tree<int> S;
void solve() {
    scanf("%d",&n);
    S.Init();
    int tot=0;
    for(o=1;o<=n;++o){
        int op,x; 
        scanf("%d%d",&op,&x);
        if(op==1){
            S.Insert(S.rt, x);
        }else if(op==2){
            S.Delete(S.rt, x);   
        }else if(op==3){
            printf("%d\n",S.getrank(S.rt, x));
        }else if(op==4){
            printf("%d\n",S.getval(S.rt, x));
        }else if(op==5){
            printf("%d\n",S.getpre(S.rt, x));
        }else if(op==6){
            printf("%d\n",S.getnxt(S.rt, x));
        }
    }
}
int main() {
    solve(); 
    return 0;
}

P3369: 250ms

指针版本(面向对象), 无重复B+树, 有内存泄露问题, 锻炼石山纠错能力 x2

这份代码看着整洁了不少, 速度稍慢

虽然答案正确, 但是内存泄露

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8 + 10;
int n, tot, valcnt;
template <typename T> class Node;
enum type {INTERNAL, LEAF};
template <typename T> struct Value{
public:
    T value;
    int count;
    Value<T>(T value, int count) : value(value), count(count) {++valcnt;}
    Value<T>() {}
    ~Value<T>() {--valcnt;}
    bool operator<(const Value<T> &x) const{
        return value < x.value;
    }
};
template <typename T> class Node{
public:
    static const int M = 3, m = (M - 1) / 2;
    Node<T> *fa;
    Node<T> *nxt;
    Node<T> *pre;
    Node<T> **son;
    Value<T> **val;
    int cnt, sz; // cnt: num of val, <= M - 1; when >= M, split
    type t;
    Node<T>(type t, Node<T> *fa) : t(t), fa(fa){
        ++tot;
        nxt = pre = NULL, cnt = sz = 0;
        val = (Value<T> **)malloc(sizeof(Value<T> *) * M);
        son = (Node<T> **)malloc(sizeof(Node<T> *) * (M + 1));
        for (int i = 0; i <= M; ++i){
            if (i < M) val[i] = NULL;
            son[i] = NULL;
        }
    }
    Node<T>() {}
    ~Node<T>() {
        --tot;
        delete [] son;
        delete [] val;
    }
};
template <typename T> class BPlusTree{
public:
    static const int M = 3, m = (M - 1) / 2;
private:
    void insert_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val);
    void insert_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val);
    void delete_left_by_id(Node<T> *u, int id);
    void delete_right_by_id(Node<T> *u, int id);
    void linkin(Node<T> *u, Node<T> *v);
    void linkout(Node<T> *u, Node<T> *v);
    void split(Node<T> *u);
    void pushup(Node<T> *u);
    void merge(Node<T> *u, Node<T> *v);
    void change_parent(Node<T> *u, Value<T> *pre, Value<T> *now);
    void fix(Node<T> *u);
    int get_id(Node<T> *u);
    void clear(Node<T> *u){
        if(!u) return;
        for(int i = 0; i < u->cnt; ++i){
            delete u->val[i], u->val[i] = NULL; // this line causes segment fault
        }
        for(int i = 0; i <= u->cnt; ++i){
            if(u->son[i]) clear(u->son[i]);
        }
        delete u, u = nullptr;
    }
public:
    Node<T> *root;
    void insert(Node<T> *u, T val);
    void erase(Node<T> *u, T val);
    int getrank(Node<T> *x, T val);
    T getval(Node<T> *x, int rank);
    int getpre(Node<T> *x, T val);
    int getnxt(Node<T> *x, T val);
    BPlusTree<T>() { root = NULL; }
    ~BPlusTree<T>() { clear(root); }
};
template <typename T> int BPlusTree<T>::get_id(Node<T> *u){
    Node<T> *fa = u->fa;
    if (!fa) return 0;
    for (int i = 0; i <= fa->cnt; ++i) 
        if (fa->son[i] == u) return i;
}
template <typename T> void BPlusTree<T>::linkin(Node<T> *u, Node<T> *v){
    Node<T> *nxt = u->nxt; // double linked list, insert v
    v->nxt = u->nxt, v->pre = u, u->nxt = v;
    if(nxt) nxt->pre = v;
}
template <typename T> void BPlusTree<T>::linkout(Node<T> *u, Node<T> *v){
    Node<T> *nxt = v->nxt; // double linked list, delete v
    u->nxt = nxt, v->nxt = NULL, v->pre = NULL;
    if (nxt) nxt->pre = u;
}
template <typename T> void BPlusTree<T>::pushup(Node<T> *u){
    if(!u) return;
    u->sz = 0;
    if (u->t == LEAF){
        for (int i = 0; i < u->cnt; ++i) u->sz += u->val[i]->count;
    }else{
        for (int i = 0; i <= u->cnt; ++i) u->sz += u->son[i]->sz;
    }
}
template <typename T> void BPlusTree<T>::change_parent(Node<T> *u, Value<T> *pre, Value<T> *now){
    u = u->fa;
    if (pre == now) return;
    while (u){ // INTERNAL
        for (int i = u->cnt - 1; i >= 0; --i){
            if (u->val[i] == pre){
                u->val[i] = now;
                return;
            }
        }
        u = u->fa;
    }
}
template <typename T> void BPlusTree<T>::insert_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val){ 
    // insert val[id] and son[id]
    for (int i = u->cnt; i >= id; --i){ 
        if (i >= 1) u->val[i] = u->val[i - 1];
        u->son[i + 1] = u->son[i];
    }
    if (u->t == INTERNAL) u->son[id] = s, s->fa = u;
    else if (id == 0) change_parent(u, u->val[0], val);
    u->val[id] = val;
    ++u->cnt;
    pushup(u);
}
template <typename T> void BPlusTree<T>::insert_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val){ 
    // insert val[id] and son[id + 1]
    for (int i = u->cnt; i >= id + 1; --i){ 
        u->val[i] = u->val[i - 1];
        u->son[i + 1] = u->son[i];
    }
    if (u->t == INTERNAL) u->son[id + 1] = s, s->fa = u;
    else if (id == 0) change_parent(u, u->val[0], val);
    u->val[id] = val;
    ++u->cnt;
    pushup(u);
}
template <typename T> void BPlusTree<T>::delete_left_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id]
    Value<T> *deleted_val = u->val[id];
    for (int i = id + 1; i <= u->cnt; ++i){
        if (i < u->cnt) u->val[i - 1] = u->val[i];
        u->son[i - 1] = u->son[i];
    }
    u->val[u->cnt - 1] = NULL;
    u->son[u->cnt] = NULL;
    if (u->t == LEAF && id == 0) change_parent(u, deleted_val, u->val[0]);
    u->cnt--;
    pushup(u);
}
template <typename T> void BPlusTree<T>::delete_right_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id + 1]
    Value<T> *deleted_val = u->val[id];
    for (int i = id + 1; i < u->cnt; ++i){
        u->val[i - 1] = u->val[i];
        u->son[i] = u->son[i + 1];
    }
    u->val[u->cnt - 1] = NULL;
    u->son[u->cnt] = NULL;
    if (u->t == LEAF && id == 0) change_parent(u, deleted_val, u->val[0]);
    u->cnt--;
    pushup(u);
}
template <typename T> void BPlusTree<T>::split(Node<T> *u){
    int mid = (u->t == LEAF) ? M / 2 : (M - 1) / 2;
    Node<T> *fa = u->fa;
    if (!fa){
        root = fa = new Node<T>(INTERNAL, NULL);
        fa->son[0] = u, u->fa = fa;
    }
    Node<T> *v = new Node<T>(u->t, fa);
    int id = get_id(u);
    insert_right_by_id(fa, id, v, u->val[mid]);
    if (u->t == LEAF){
        for (int i = mid; i < u->cnt; ++i){
            v->val[i - mid] = u->val[i], u->val[i] = NULL;
        }
        u->cnt = mid, v->cnt = M - mid;
        linkin(u, v);
    }else{
        for (int i = mid + 1; i <= u->cnt; ++i){
            if (i < u->cnt) v->val[i - mid - 1] = u->val[i], u->val[i] = NULL;
            v->son[i - mid - 1] = u->son[i], u->son[i]->fa = v, u->son[i] = NULL;
        }
        u->cnt = mid, v->cnt = M - mid - 1;
    }
    pushup(u), pushup(v);
}

template <typename T> void BPlusTree<T>::insert(Node<T> *u, T val){
    if (!root){
        root = new Node<T>(LEAF, NULL);
        insert_right_by_id(root, 0, NULL, new Value<T>(val, 1));
        pushup(root);
        return;
    }
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < u->val[i]->value) break;
        else if (u->t == LEAF && val <= u->val[i]->value) break;
    }
    if (u->t == INTERNAL) insert(u->son[i], val);
    else{
        if (i < u->cnt && val == u->val[i]->value){
            ++u->val[i]->count, pushup(u);
            return;
        }
        insert_right_by_id(u, i, NULL, new Value<T>(val, 1));
    }
    if (u->cnt >= M) split(u);
    pushup(u);
}

template <typename T> void BPlusTree<T>::merge(Node<T> *u, Node<T> *v){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    Value<T> *val = fa->val[id];
    //v->fa = NULL;
    if (u->t == LEAF){
        if (!u->cnt) change_parent(u, NULL, v->val[0]); // always change parent when i == 0 and LEAF
        for (int i = 0; i < v->cnt; ++i)
            u->val[u->cnt++] = v->val[i], v->val[i] = NULL;
        v->cnt = 0;
        linkout(u, v);
    }else{
        insert_right_by_id(u, u->cnt, v->son[0], val);
        for (int i = 0; i < v->cnt; ++i){
            u->val[u->cnt++] = v->val[i], v->val[i] = NULL;
            u->son[u->cnt] = v->son[i + 1], v->son[i + 1]->fa = u, v->son[i + 1] = NULL;
        }
        v->cnt = 0;
    }
    delete_right_by_id(fa, id); // what if this sentence is put in front of if (u->t == LEAF) sentence?
    delete v, v = nullptr;
    pushup(u);
}
template <typename T> void BPlusTree<T>::fix(Node<T> *u){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    if (!fa) return;
    if (id > 0 && fa->son[id - 1]->cnt > m){ // borrow pre
        Node<T> *v = fa->son[id - 1];
        Node<T> *s = (u->t == LEAF) ? NULL : v->son[v->cnt];
        Value<T> *pre = (u->t == LEAF) ? v->val[v->cnt - 1] : fa->val[id - 1];
        if (u->t == INTERNAL) fa->val[id - 1] = v->val[v->cnt - 1]; // change parent
        insert_left_by_id(u, 0, s, pre);
        delete_right_by_id(v, v->cnt - 1);
        pushup(u), pushup(v);
    }else if (id < fa->cnt && fa->son[id + 1]->cnt > m){ // borrow nxt
        Node<T> *v = fa->son[id + 1];
        Node<T> *s = (u->t == LEAF) ? NULL : v->son[0];
        Value<T> *nxt = (u->t == LEAF) ? v->val[0] : fa->val[id];
        if (u->t == INTERNAL) fa->val[id] = v->val[0]; // change parent
        delete_left_by_id(v, 0);               
        insert_right_by_id(u, u->cnt, s, nxt); 
        pushup(u), pushup(v);
    }else{
        if (id > 0) merge(fa->son[id - 1], u);
        else merge(u, fa->son[id + 1]);
    }
}
template <typename T> void BPlusTree<T>::erase(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < u->val[i]->value) break;
        else if (u->t == LEAF && val <= u->val[i]->value) break;
    }
    if (u->t == INTERNAL) erase(u->son[i], val);
    else{
        if (i >= u->cnt || u->val[i]->value != val) return; // not found
        if (u->val[i]->count > 1){
            --u->val[i]->count, pushup(u);
            return;
        }
        delete_right_by_id(u, i);
    }
    if (u == root && !u->cnt){
        root = u->son[0];
        if(root) root->fa = NULL, pushup(root);
        delete u, u = nullptr;
        return;
    }
    if (u->cnt < m) fix(u);
    pushup(u);
}
template <typename T> int BPlusTree<T>::getrank(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < u->val[i]->value) break;
        else if (u->t == LEAF && val <= u->val[i]->value) break;
    }
    if (u->t == INTERNAL){
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->son[j]->sz;
        return rank + getrank(u->son[i], val);
    }else{
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->val[j]->count;
        return rank + 1;
    }
}
template <typename T> T BPlusTree<T>::getval(Node<T> *u, int rank){
    int i = 0;
    if (u->t == INTERNAL){
        for (; i <= u->cnt; ++i){
            if (rank <= u->son[i]->sz) break;
            else rank -= u->son[i]->sz;
        }
        return getval(u->son[i], rank);
    }else{
        for (; i < u->cnt; ++i){
            if (rank >= 1 && rank <= u->val[i]->count) return u->val[i]->value;
            else rank -= u->val[i]->count;
        }
    }
}

template <typename T> int BPlusTree<T>::getpre(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < u->val[i]->value) break;
        else if (u->t == LEAF && val <= u->val[i]->value) break;
    }
    if (u->t == INTERNAL) return getpre(u->son[i], val);
    else{
        if (i == 0) u = u->pre, i = u->cnt;
        assert(u != NULL);
        return u->val[i - 1]->value;
    }
}
template <typename T>int BPlusTree<T>::getnxt(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i)
        if (val < u->val[i]->value) break;
    if (u->t == INTERNAL) return getnxt(u->son[i], val);
    else{
        if (i == u->cnt) u = u->nxt, i = 0;
        assert(u != NULL);
        return u->val[i]->value;
    }
}
void solve(){
    scanf("%d", &n);
    BPlusTree<int> *S = new BPlusTree<int>();
    for (int i = 1; i <= n; ++i){
        int op, x;
        scanf("%d%d", &op, &x);
        if (op == 1){
            S->insert(S->root, x);
        }else if (op == 2){
            S->erase(S->root, x);
        }else if (op == 3){
            printf("%d\n", S->getrank(S->root, x));
        }else if (op == 4){
            printf("%d\n", S->getval(S->root, x));
        }else if (op == 5){
            printf("%d\n", S->getpre(S->root, x));
        }else if (op == 6){
            printf("%d\n", S->getnxt(S->root, x));
        }
    }
    delete S;
}
int main(){
    for(int i=1;i<=1000;++i){
        freopen("P3369_10.in", "r", stdin);
        freopen("P3369_10.out", "w", stdout);
        solve();
    }
    return 0;
}

P3369: 300ms

注意这段代码的内存泄露会导致运行 \(1000\) 次占用内存越来越多

主要问题

这份代码中, 树中的叶子与内部节点可能会有相同值的 value 对象

而这种写法将两个 val 指针指向同一个 value 对象, 所以删除 val 时会删除同一个对象两次而出问题

所以一种解决办法是只遍历树的叶子删除, 因为B+树的真值只存在叶子中

也可以出现叶子与内部节点有相同值时, 内部节点新建一个 value 对象

或者可以维护一下一个对象是否被删除, 但这样会慢

还可以把裸指针改成 shared_ptr 自动管理内存

裸指针版本(面向对象), 无重复B+树, 无内存泄露

注意

这份代码在我的电脑上跑没问题(AC + 无内存泄露), 而 luogu P3369: RE

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8 + 10;
int n, valcnt;
template <typename T> class Node;
enum type {INTERNAL, LEAF};
template <typename T> struct Value{
public:
    T value;
    int count;
    Value<T>(T value, int count) : value(value), count(count) {++valcnt;}
    Value<T>() {}
    ~Value<T>() {--valcnt;}
    bool operator<(const Value<T> &x) const{
        return value < x.value;
    }
};
template <typename T> class Node{
public:
    static const int M = 3, m = (M - 1) / 2;
    Node<T> *fa, *nxt, *pre;
    Node<T> **son;
    Value<T> **val;
    int cnt, sz; // cnt: num of val, <= M - 1; when >= M, split
    type t;
    Node<T>(type t, Node<T> *fa) : t(t), fa(fa){
        nxt = pre = NULL, cnt = sz = 0;
        val = (Value<T> **)malloc(sizeof(Value<T> *) * M);
        son = (Node<T> **)malloc(sizeof(Node<T> *) * (M + 1));
        for (int i = 0; i <= M; ++i){
            if (i < M) val[i] = NULL;
            son[i] = NULL;
        }
    }
    Node<T>() {}
    ~Node<T>() {
        // free(son), free(val); // add this line will cause luogu P3369 RE
        delete [] son, delete [] val; // add this line will cause luogu P3369 RE
    }
};
template <typename T> class BPlusTree{
public:
    static const int M = 3, m = (M - 1) / 2;
private:
    void insert_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val);
    void insert_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val);
    Value<T>* delete_left_by_id(Node<T> *u, int id);
    Value<T>* delete_right_by_id(Node<T> *u, int id);
    void linkin(Node<T> *u, Node<T> *v);
    void linkout(Node<T> *u, Node<T> *v);
    void split(Node<T> *u);
    void pushup(Node<T> *u);
    void merge(Node<T> *u, Node<T> *v);
    void change_parent(Node<T> *u, Value<T> *pre, Value<T> *now);
    void fix(Node<T> *u);
    int get_id(Node<T> *u);
    void clear(Node<T> *u){
        if(!u) return;
        for(int i = 0; i <= u->cnt; ++i){
            clear(u->son[i]);
        }
        delete u, u = nullptr;
    }
    void destroy(Node<T> *u){
        while(u && u->t == INTERNAL) u = u->son[0];
        while(u){
            for(int i = 0; i < u->cnt; ++i){
                delete u->val[i], u->val[i] = nullptr;
            }
            u = u->nxt;
        }
    }
public:
    Node<T> *root;
    void insert(Node<T> *u, T val);
    void erase(Node<T> *u, T val);
    int getrank(Node<T> *x, T val);
    T getval(Node<T> *x, int rank);
    int getpre(Node<T> *x, T val);
    int getnxt(Node<T> *x, T val);
    BPlusTree<T>() { root = NULL; }
    ~BPlusTree<T>() { destroy(root); clear(root); }
};
template <typename T> int BPlusTree<T>::get_id(Node<T> *u){
    Node<T> *fa = u->fa;
    if (!fa) return 0;
    for (int i = 0; i <= fa->cnt; ++i) 
        if (fa->son[i] == u) return i;
}
template <typename T> void BPlusTree<T>::linkin(Node<T> *u, Node<T> *v){
    Node<T> *nxt = u->nxt; // double linked list, insert v
    v->nxt = u->nxt, v->pre = u, u->nxt = v;
    if(nxt) nxt->pre = v;
}
template <typename T> void BPlusTree<T>::linkout(Node<T> *u, Node<T> *v){
    Node<T> *nxt = v->nxt; // double linked list, delete v
    u->nxt = nxt, v->nxt = NULL, v->pre = NULL;
    if (nxt) nxt->pre = u;
}
template <typename T> void BPlusTree<T>::pushup(Node<T> *u){
    if(!u) return;
    u->sz = 0;
    if (u->t == LEAF){
        for (int i = 0; i < u->cnt; ++i) u->sz += u->val[i]->count;
    }else{
        for (int i = 0; i <= u->cnt; ++i) u->sz += u->son[i]->sz;
    }
}
template <typename T> void BPlusTree<T>::change_parent(Node<T> *u, Value<T> *pre, Value<T> *now){
    u = u->fa;
    if (pre == now) return;
    for(; u; u = u->fa){ // INTERNAL
        for (int i = u->cnt - 1; i >= 0; --i){
            if (u->val[i] == pre){
                u->val[i] = now;
                return;
            }
        }
    }
}
template <typename T> void BPlusTree<T>::insert_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val){ 
    // insert val[id] and son[id]
    for (int i = u->cnt; i >= id; --i){ 
        if (i >= 1) u->val[i] = u->val[i - 1];
        u->son[i + 1] = u->son[i];
    }
    if (u->t == INTERNAL) u->son[id] = s, s->fa = u;
    else if (id == 0) change_parent(u, u->val[0], val);
    u->val[id] = val;
    ++u->cnt, pushup(u);
}
template <typename T> void BPlusTree<T>::insert_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val){ 
    // insert val[id] and son[id + 1]
    for (int i = u->cnt; i >= id + 1; --i){ 
        u->val[i] = u->val[i - 1];
        u->son[i + 1] = u->son[i];
    }
    if (u->t == INTERNAL) u->son[id + 1] = s, s->fa = u;
    else if (id == 0) change_parent(u, u->val[0], val);
    u->val[id] = val;
    ++u->cnt, pushup(u);
}
template <typename T> Value<T>* BPlusTree<T>::delete_left_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id]
    Value<T> *deleted_val = u->val[id];
    for (int i = id + 1; i <= u->cnt; ++i){
        if (i < u->cnt) u->val[i - 1] = u->val[i];
        u->son[i - 1] = u->son[i];
    }
    u->val[u->cnt - 1] = NULL;
    u->son[u->cnt] = NULL;
    if (u->t == LEAF && id == 0) change_parent(u, deleted_val, u->val[0]);
    u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> Value<T>* BPlusTree<T>::delete_right_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id + 1]
    Value<T> *deleted_val = u->val[id];
    for (int i = id + 1; i < u->cnt; ++i){
        u->val[i - 1] = u->val[i];
        u->son[i] = u->son[i + 1];
    }
    u->val[u->cnt - 1] = NULL;
    u->son[u->cnt] = NULL;
    if (u->t == LEAF && id == 0) change_parent(u, deleted_val, u->val[0]);
    u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> void BPlusTree<T>::split(Node<T> *u){
    int mid = (u->t == LEAF) ? M / 2 : (M - 1) / 2;
    Node<T> *fa = u->fa;
    if (!fa) root = fa = new Node<T>(INTERNAL, NULL), fa->son[0] = u, u->fa = fa;
    Node<T> *v = new Node<T>(u->t, fa);
    int id = get_id(u);
    insert_right_by_id(fa, id, v, u->val[mid]);
    if (u->t == LEAF){
        for (int i = mid; i < u->cnt; ++i){
            v->val[i - mid] = u->val[i], u->val[i] = NULL;
        }
        u->cnt = mid, v->cnt = M - mid;
        linkin(u, v);
    }else{
        for (int i = mid + 1; i <= u->cnt; ++i){
            if (i < u->cnt) v->val[i - mid - 1] = u->val[i], u->val[i] = NULL;
            v->son[i - mid - 1] = u->son[i], u->son[i]->fa = v, u->son[i] = NULL;
        }
        u->cnt = mid, v->cnt = M - mid - 1;
    }
    pushup(u), pushup(v);
}

template <typename T> void BPlusTree<T>::insert(Node<T> *u, T val){
    if (!root){
        root = new Node<T>(LEAF, NULL);
        insert_right_by_id(root, 0, NULL, new Value<T>(val, 1));
        pushup(root);
        return;
    }
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < u->val[i]->value) break;
        else if (u->t == LEAF && val <= u->val[i]->value) break;
    }
    if (u->t == INTERNAL) insert(u->son[i], val);
    else{
        if (i < u->cnt && val == u->val[i]->value){
            ++u->val[i]->count, pushup(u);
            return;
        }
        insert_right_by_id(u, i, NULL, new Value<T>(val, 1));
    }
    if (u->cnt >= M) split(u);
    pushup(u);
}
template <typename T> void BPlusTree<T>::merge(Node<T> *u, Node<T> *v){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    Value<T> *val = fa->val[id];
    if (u->t == LEAF){
        if (!u->cnt) change_parent(u, NULL, v->val[0]); // always change parent when i == 0 and LEAF
        for (int i = 0; i < v->cnt; ++i)
            u->val[u->cnt++] = v->val[i], v->val[i] = NULL;
        v->cnt = 0;
        linkout(u, v);
    }else{
        insert_right_by_id(u, u->cnt, v->son[0], val);
        for (int i = 0; i < v->cnt; ++i){
            u->val[u->cnt++] = v->val[i], v->val[i] = NULL;
            u->son[u->cnt] = v->son[i + 1], v->son[i + 1]->fa = u, v->son[i + 1] = NULL;
        }
        v->cnt = 0;
    }
    delete_right_by_id(fa, id); // what if this sentence is put in front of if (u->t == LEAF) sentence?
    delete v, v = nullptr;
    pushup(u);
}
template <typename T> void BPlusTree<T>::fix(Node<T> *u){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    if (!fa) return;
    if (id > 0 && fa->son[id - 1]->cnt > m){ // borrow pre
        Node<T> *v = fa->son[id - 1];
        Node<T> *s = (u->t == LEAF) ? NULL : v->son[v->cnt];
        Value<T> *pre = (u->t == LEAF) ? v->val[v->cnt - 1] : fa->val[id - 1];
        if (u->t == INTERNAL) fa->val[id - 1] = v->val[v->cnt - 1]; // change parent
        insert_left_by_id(u, 0, s, pre);
        delete_right_by_id(v, v->cnt - 1);
        pushup(u), pushup(v);
    }else if (id < fa->cnt && fa->son[id + 1]->cnt > m){ // borrow nxt
        Node<T> *v = fa->son[id + 1];
        Node<T> *s = (u->t == LEAF) ? NULL : v->son[0];
        Value<T> *nxt = (u->t == LEAF) ? v->val[0] : fa->val[id];
        if (u->t == INTERNAL) fa->val[id] = v->val[0]; // change parent
        delete_left_by_id(v, 0);               
        insert_right_by_id(u, u->cnt, s, nxt); 
        pushup(u), pushup(v);
    }else{
        if (id > 0) merge(fa->son[id - 1], u);
        else merge(u, fa->son[id + 1]);
    }
}
template <typename T> void BPlusTree<T>::erase(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < u->val[i]->value) break;
        else if (u->t == LEAF && val <= u->val[i]->value) break;
    }
    if (u->t == INTERNAL) erase(u->son[i], val);
    else{
        if (i >= u->cnt || u->val[i]->value != val) return; // not found
        if (u->val[i]->count > 1){
            --u->val[i]->count, pushup(u);
            return;
        }
        Value<T> *deleted_value = delete_right_by_id(u, i);
        delete deleted_value, deleted_value = nullptr;
    }
    if (u == root && !u->cnt){
        root = u->son[0];
        if(root) root->fa = NULL, pushup(root);
        delete u, u = nullptr;
        return;
    }
    if (u->cnt < m) fix(u);
    pushup(u);
}
template <typename T> int BPlusTree<T>::getrank(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < u->val[i]->value) break;
        else if (u->t == LEAF && val <= u->val[i]->value) break;
    }
    if (u->t == INTERNAL){
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->son[j]->sz;
        return rank + getrank(u->son[i], val);
    }else{
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->val[j]->count;
        return rank + 1;
    }
}
template <typename T> T BPlusTree<T>::getval(Node<T> *u, int rank){
    int i = 0;
    if (u->t == INTERNAL){
        for (; i <= u->cnt; ++i){
            if (rank <= u->son[i]->sz) break;
            else rank -= u->son[i]->sz;
        }
        return getval(u->son[i], rank);
    }else{
        for (; i < u->cnt; ++i){
            if (rank >= 1 && rank <= u->val[i]->count) return u->val[i]->value;
            else rank -= u->val[i]->count;
        }
    }
}
template <typename T> int BPlusTree<T>::getpre(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < u->val[i]->value) break;
        else if (u->t == LEAF && val <= u->val[i]->value) break;
    }
    if (u->t == INTERNAL) return getpre(u->son[i], val);
    else{
        if (i == 0) u = u->pre, i = u->cnt;
        assert(u != NULL);
        return u->val[i - 1]->value;
    }
}
template <typename T>int BPlusTree<T>::getnxt(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i)
        if (val < u->val[i]->value) break;
    if (u->t == INTERNAL) return getnxt(u->son[i], val);
    else{
        if (i == u->cnt) u = u->nxt, i = 0;
        assert(u != NULL);
        return u->val[i]->value;
    }
}
void solve(){
    scanf("%d", &n);
    BPlusTree<int> *S = new BPlusTree<int>();
    int tt = 0;
    for (int i = 1; i <= n; ++i){
        int op, x;
        scanf("%d%d", &op, &x);
        if (op == 1){
            S->insert(S->root, x);
        }else if (op == 2){
            S->erase(S->root, x);
        }else if (op == 3){
            printf("%d\n", S->getrank(S->root, x));
        }else if (op == 4){
            printf("%d\n", S->getval(S->root, x));
        }else if (op == 5){
            printf("%d\n", S->getpre(S->root, x));
        }else if (op == 6){
            printf("%d\n", S->getnxt(S->root, x));
        }
    }
    delete S;
}
int main(){
    // for(int i=1;i<=1000;++i){
    //     freopen("P3369_10.in", "r", stdin);
    //     freopen("P3369_10.out", "w", stdout);
    //     solve();
    // }
    solve();
    return 0;
}

P3369: 300ms

跳表版本, 但答案错误且内存泄露, 锻炼石山纠错能力 x3

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8 + 10;
int n, valcnt, o, m;
const int MAXL = 20;
const double p = 0.5;


template <typename T> struct Value{
    public:
    T value;
    int count;
    Value<T>(T value, int count) : value(value), count(count) {++valcnt;}
    Value<T>() {}
    ~Value<T>() {--valcnt;}
    bool operator <(const Value<T> &x) const{
        return value < x.value;
    }
};


template <typename T>
class SkipList;
template <typename T>
class SLNode
{
public:
    SLNode<T> **forward;
    int *next;
    Value<T> *key;
    Value<T> *value;
    int level;
    SLNode<T>() {}
    ~SLNode<T>() {
        delete [] forward;
        delete [] next;
    }
    SLNode<T>(Value<T> * key, Value<T> * value) : key(key), value(value)
    {
        next = new int [MAXL + 1];
        forward = new SLNode<T> *[MAXL + 1]; 
        for (int i = 0; i <= MAXL; ++i)
            forward[i] = NULL, next[i] = 0;
        level = RandomLevel();
    }
    int RandomLevel()
    {
        int lv = 0;
        int maxn = 1023;
        while (lv < MAXL && rand() % maxn < (int)(p * maxn))
            ++lv;
        return lv;
    }
    friend class SkipList<T>;
};
template <typename T>
class SkipList
{
public:
    static const int MAXL = 20, INF = 1e9 + 10;
    int level;
    int length;
    SLNode<T> *head;
    SkipList<T>() { head = new SLNode<T>(0, 0), level = 0, length = 0; }
    // SkipList<T>(int level) : level(level) { head = new SLNode<T>(0, 0), length = 0; }
    ~SkipList<T>() {
        SLNode<T> *p = head;
        while(p){
            SLNode<T> *q = p->forward[0];
            delete p, p = q;
        }   
    }
    SLNode<T>* operator [](int rank){ // from 0
        ++rank;
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i)
        {
            while (p->forward[i] != NULL && p->next[i] < rank)
                rank -= p->next[i], p = p->forward[i];
        }
        p = p->forward[0];
        return p;
    }
    SLNode<T>* getnode(int rank){ // from 1
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i)
        {
            while (p->forward[i] != NULL && p->next[i] < rank)
                rank -= p->next[i], p = p->forward[i];
        }
        p = p->forward[0];
        return p;
    }
    Value<T> * getvalue(int rank){ // from 1
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i)
        {
            while (p->forward[i] != NULL && p->next[i] < rank)
                rank -= p->next[i], p = p->forward[i];
        }
        p = p->forward[0];
        return p->value;
    }
    int getrank(Value<T> * key){
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i)
        {
            while (p->forward[i] != NULL && p->forward[i]->key->value < key->value)
                now += p->next[i], p = p->forward[i];
        }
        return now + 1;
    }
    Value<T> * kth(int rank)
    {
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i)
        {
            while (p->forward[i] != NULL && p->next[i] < rank)
                rank -= p->next[i], p = p->forward[i];
        }
        p = p->forward[0];
        return p->key;
    }
    Value<T> * pre(Value<T> * key)
    {
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i)
        {
            while (p->forward[i] != NULL && p->forward[i]->key->value < key->value)
                p = p->forward[i];
        }
        return p->key;
    }
    Value<T> * nxt(Value<T> * key)
    {
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i)
        {
            while (p->forward[i] != NULL && p->forward[i]->key->value <= key->value)
                p = p->forward[i];
        }
        p = p->forward[0];
        if(p) return p->key;
        return INF;
    }
    void insert(Value<T> * key, Value<T> * value)
    {
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i)
        {
            while (p->forward[i] != NULL && p->forward[i]->key->value < key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++; // now += p->next[0]
        SLNode<T> *NewNode = new SLNode<T>(key, value);
        if (level < NewNode->level)
        {
            NewNode->level = head->level = ++level;
            update[level] = head, pos[level] = 0;
        }
        for (int i = 0; i <= level; ++i)
        {
            p = update[i];
            if (i <= NewNode->level)
            {
                NewNode->forward[i] = p->forward[i];
                if (p->forward[i])
                    NewNode->next[i] = p->next[i] - (now - pos[i]) + 1;
                else
                    NewNode->next[i] = 0;
                p->next[i] = now - pos[i];
                p->forward[i] = NewNode;
            }
            else
            {
                if (p->forward[i])
                    p->next[i]++;
                else p->next[i] = 0;
            }
        }
        length++;
    }
    bool erase(Value<T> * key)
    {
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        // if(!key){
        //     SLNode<T> *q = p;
        //     int rank = 0;
        //     while(q && q->forward[0]->key != NULL) q = q->forward[0], ++rank;
        //     q = q->forward[0], ++rank;
        //     for (int i = level; i >= 0; --i){
        //         while (p->forward[i] != NULL && now + p->next[i] < rank)
        //             now += p->next[i], p = p->forward[i];
        //         update[i] = p;
        //         pos[i] = now;
        //     }
        //     p = p->forward[0], now++;
        // }else{
            for (int i = level; i >= 0; --i){
                while (p->forward[i] != NULL && p->forward[i]->key->value < key->value)
                    now += p->next[i], p = p->forward[i];
                update[i] = p;
                pos[i] = now;
            }
            p = p->forward[0], now++;
            if (!p || p->key->value != key->value)
                return false;
        // }
        for (int i = 0; i <= level; ++i)
        {
            if (update[i]->forward[i] != p)
            {
                if (update[i]->forward[i])
                    update[i]->next[i]--;
                else update[i]->next[i] = 0;
            }
            else
            {
                update[i]->forward[i] = p->forward[i];
                update[i]->next[i] += p->next[i] - 1;
            }
        }
        delete p;
        while (level > 0 && head->forward[level] == NULL)
            level--;
        head->level = level;
        length--;
        return true;
    }
    void print()
    {
        SLNode<T> *p = head;
        while (p)
        {
            cout << p->key << " ";
            if (p == head)
                cout << level << ": ";
            else
                cout << p->level << ": ";
            for (int i = level; i >= 0; --i)
            {
                if (p->forward[i] == NULL)
                    cout << "NULL ";
                else
                    cout << "(" << p->forward[i]->key << ", " << p->next[i] << ") ";
            }
            cout << endl;
            p = p->forward[0];
        }
        cout << "length: " << length << endl;
    }

};


template <typename T>
pair<SkipList<T>*, SkipList<T>*> splitlist(SkipList<T>* u, int rank){
    SkipList<T>* v = new SkipList<T>();
    SLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    SLNode<T> *p = u->head;
    int now = 0, level = u->level;
    for (int i = level; i >= 0; --i)
    {
        while (p->forward[i] != NULL && now + p->next[i] < rank)
            now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    v->level = level, v->head->level = level;
    v->length = u->length - now + 1, u->length = now - 1;

    for (int i = 0; i <= level; ++i)
    {
        p = update[i];
        v->head->forward[i] = p->forward[i];
        if (p->forward[i])
            v->head->next[i] = p->next[i] - (now - pos[i]) + 1;
        else
            v->head->next[i] = 0;
        p->next[i] = 0;
        p->forward[i] = NULL;
    }
    return make_pair(u, v);
}


template <typename T>
SkipList<T>* mergelist(SkipList<T>* u, SkipList<T>* v){
    SLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    SLNode<T> *p = u->head;
    int now = 0;
    for (int i = u->level; i >= 0; --i)
    {
        while (p->forward[i] != NULL)
            now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]

    for (int i = 0; i <= v->level; ++i){
        if(i > u->level){
            u->head->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) u->head->next[i] = u->length + v->head->next[i];
            else u->head->next[i] = 0;
        }else{
            update[i]->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) update[i]->next[i] = (u->length - pos[i]) + v->head->next[i];
            else update[i]->next[i] = 0;
        }
        v->head->forward[i] = NULL;
    }
    u->level = max(u->level, v->level);
    u->head->level = u->level;
    u->length += v->length;
    // delete v; // v will be deleted in B+ tree (when Node is deleted, Node->Value will also be deleted)
    return u;
}


enum type {INTERNAL, LEAF};
template <typename T> class Node{
public:
    static const int M = 3, m = (M - 1) / 2;
    Node<T> *fa, *nxt, *pre;
    SkipList<T> *val;
    Node<T> **son;
    int cnt, sz; // cnt: num of val, <= M - 1; when >= M, split
    type t;
    Node<T>(type t, Node<T> *fa) : t(t), fa(fa){
        nxt = pre = NULL, cnt = sz = 0;
        val = new SkipList<T>();
        son = (Node<T> **)malloc(sizeof(Node<T> *) * (M + 1));
        for (int i = 0; i <= M; ++i) son[i] = NULL;
    }
    Node<T>() {}
    ~Node<T>() {
        // free(son), free(val); // add this line will cause luogu P3369 RE
        // delete [] son; // add this line will cause luogu P3369 RE
        // delete val;
        // delete [] val; 
        // delete son, delete val;
        // delete List;
    }
};
template <typename T> class BPlusTree{
public:
    static const int M = 3, m = (M - 1) / 2;
private:
    void insert_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val);
    void insert_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val);
    Value<T>* delete_left_by_id(Node<T> *u, int id);
    Value<T>* delete_right_by_id(Node<T> *u, int id);
    void linkin(Node<T> *u, Node<T> *v);
    void linkout(Node<T> *u, Node<T> *v);
    void split(Node<T> *u);
    void pushup(Node<T> *u);
    void merge(Node<T> *u, Node<T> *v);
    void change_parent(Node<T> *u, Value<T> *pre, Value<T> *now);
    void fix(Node<T> *u);
    int get_id(Node<T> *u);
    void clear(Node<T> *u){
        if(!u) return;
        for(int i = 0; i <= u->cnt; ++i){
            clear(u->son[i]);
        }
        delete u, u = nullptr;
    }
    void destroy(Node<T> *u){
        while(u && u->t == INTERNAL) u = u->son[0];
        while(u){
            for(int i = 0; i < u->cnt; ++i){
                delete (*u->val)[i]->key, (*u->val)[i]->key = nullptr;
            }
            u = u->nxt;
        }
    }
public:
    Node<T> *root;
    void insert(Node<T> *u, T val);
    void erase(Node<T> *u, T val);
    int getrank(Node<T> *x, T val);
    T getval(Node<T> *x, int rank);
    int getpre(Node<T> *x, T val);
    int getnxt(Node<T> *x, T val);
    BPlusTree<T>() { root = NULL; }
    ~BPlusTree<T>() { 
        // destroy(root); 
        clear(root); 
    }
    void dfs(Node<T> *x) {
        assert(x!=NULL);
        cerr<<x<<"(type="<<(x->t==LEAF?"LEAF":"INTERNAL");
        cerr<<",id="<<get_id(x)<<",sz="<<x->sz;
        cerr<<")->[";
        SLNode<T> *p = x->val->head->forward[0];
        while(p){
            if(p->key) cerr << p->key->value << " ";
            else cerr << "NULL ";
            p = p->forward[0];
        }
        cerr<<"]";
        cerr<<endl;
        if(x->t==LEAF) return;
        for(int i=0; i<x->cnt+1; ++i) dfs(x->son[i]);
    }
};
template <typename T> int BPlusTree<T>::get_id(Node<T> *u){
    Node<T> *fa = u->fa;
    if (!fa) return 0;
    for (int i = 0; i <= fa->cnt; ++i) 
        if (fa->son[i] == u) return i;
}
template <typename T> void BPlusTree<T>::linkin(Node<T> *u, Node<T> *v){
    Node<T> *nxt = u->nxt; // double linked list, insert v
    v->nxt = u->nxt, v->pre = u, u->nxt = v;
    if(nxt) nxt->pre = v;
}
template <typename T> void BPlusTree<T>::linkout(Node<T> *u, Node<T> *v){
    Node<T> *nxt = v->nxt; // double linked list, delete v
    u->nxt = nxt, v->nxt = NULL, v->pre = NULL;
    if (nxt) nxt->pre = u;
}
template <typename T> void BPlusTree<T>::pushup(Node<T> *u){
    if(!u) return;
    u->sz = 0;
    if (u->t == LEAF){
        for (int i = 0; i < u->cnt; ++i) u->sz += (*u->val)[i]->key->count;
    }else{
        for (int i = 0; i <= u->cnt; ++i) u->sz += u->son[i]->sz;
    }
}
template <typename T> void BPlusTree<T>::change_parent(Node<T> *u, Value<T> *pre, Value<T> *now){
    u = u->fa;
    if (pre == now) return;
    for(; u; u = u->fa){ // INTERNAL
        for (int i = u->cnt - 1; i >= 0; --i){
            if ((*u->val)[i]->key == pre){
                (*u->val)[i]->key = now;
                return;
            }
        }
    }
}
template <typename T> void BPlusTree<T>::insert_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val){ 
    // insert val[id] and son[id]
    for (int i = u->cnt; i >= id; --i) u->son[i + 1] = u->son[i];
    if (u->t == INTERNAL) u->son[id] = s, s->fa = u;
    else if (id == 0){
        SLNode<T> *p = (*u->val)[0];
        if(p != NULL) change_parent(u, p->value, val);
        else change_parent(u, NULL, val); // note this 
    }
    u->val->insert(val, val);
    ++u->cnt, pushup(u);
}
template <typename T> void BPlusTree<T>::insert_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val){ 
    // insert val[id] and son[id + 1]
    for (int i = u->cnt; i >= id + 1; --i) u->son[i + 1] = u->son[i];
    if (u->t == INTERNAL) u->son[id + 1] = s, s->fa = u;  
    // else if (id == 0){   
    //     SLNode<T> *p = (*u->val)[0];
    //     if(p != NULL) change_parent(u, p->value, val);
    //     else change_parent(u, NULL, val);
    // }
    else if (id == 0) change_parent(u, p->value, val);
    u->val->insert(val, val);
    ++u->cnt, pushup(u);
}

template <typename T> Value<T>* BPlusTree<T>::delete_left_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id]
    Value<T> *deleted_val = ((*u->val)[id]) ? (*u->val)[id]->key : NULL;
    for (int i = id + 1; i <= u->cnt; ++i) u->son[i - 1] = u->son[i];
    u->val->erase(deleted_val);
    u->son[u->cnt] = NULL;
    if (u->t == LEAF && id == 0){
        SLNode<T> *p = (*u->val)[0];
        if(p != NULL) change_parent(u, deleted_val, p->value);
        else change_parent(u, deleted_val, NULL);
    }
    u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> Value<T>* BPlusTree<T>::delete_right_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id + 1]
    // Value<T> *deleted_val = ((*u->val)[id]) ? (*u->val)[id]->key : NULL;
    Value<T> *deleted_val = (*u->val)[id]->key;
    for (int i = id + 1; i < u->cnt; ++i) u->son[i] = u->son[i + 1];
    u->son[u->cnt] = NULL;
    u->val->erase(deleted_val); // if deleted_val == NULL, then is O(M), otherwise O(log M)
    // if (u->t == LEAF && id == 0){
    //     SLNode<T> *p = (*u->val)[0];
    //     if(p != NULL) change_parent(u, deleted_val, p->value); // note this sepcial judge
    //     else change_parent(u, deleted_val, NULL);
    // }
    if (u->t == LEAF && id == 0) change_parent(u, deleted_val, p->value);
    u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> void BPlusTree<T>::split(Node<T> *u){
    int mid = (u->t == LEAF) ? M / 2 : (M - 1) / 2;
    Node<T> *fa = u->fa;
    if (!fa) root = fa = new Node<T>(INTERNAL, NULL), fa->son[0] = u, u->fa = fa;
    Node<T> *v = new Node<T>(u->t, fa);
    int id = get_id(u);
    insert_right_by_id(fa, id, v, (*u->val)[mid]->key);
    if (u->t == LEAF){
        pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, mid + 1);
        u->val = p.first;
        // delete v->val;
        v->val = p.second;
        u->cnt = mid, v->cnt = M - mid;
        linkin(u, v);
    }else{
        for (int i = mid + 1; i <= u->cnt; ++i){
            v->son[i - mid - 1] = u->son[i];
            u->son[i]->fa = v, u->son[i] = NULL;
        }
        pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, mid + 1);
        u->val = p.first;
        pair<SkipList<T>*, SkipList<T>* > q = splitlist(p.second, 2);
        // delete q.first;
        // delete v->val;
        v->val = q.second;
        u->cnt = mid, v->cnt = M - mid - 1;
    }
    pushup(u), pushup(v);
}

template <typename T> void BPlusTree<T>::insert(Node<T> *u, T val){
    if (!root){
        root = new Node<T>(LEAF, NULL);
        insert_right_by_id(root, 0, NULL, new Value<T>(val, 1));
        pushup(root);
        return;
    }
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < (*u->val)[i]->key->value) break;
        else if (u->t == LEAF && val <= (*u->val)[i]->key->value) break;
    }
    if (u->t == INTERNAL) insert(u->son[i], val);
    else{
        if (i < u->cnt && val == (*u->val)[i]->key->value){
            ++(*u->val)[i]->key->count, pushup(u);
            return;
        }
        insert_right_by_id(u, i, NULL, new Value<T>(val, 1));
    }
    if (u->cnt >= M) split(u);
    pushup(u);
}
template <typename T> void BPlusTree<T>::merge(Node<T> *u, Node<T> *v){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    Value<T> *val = (*fa->val)[id]->key;
    if (u->t == LEAF){
        if (!u->cnt) change_parent(u, NULL, (*v->val)[0]->key); // always change parent when i == 0 and LEAF
        u->val = mergelist(u->val, v->val);
        // u->cnt += v->cnt; 
        v->cnt = 0;
        linkout(u, v);
    }else{
        insert_right_by_id(u, u->cnt, v->son[0], val);
        for (int i = 0; i < v->cnt; ++i){
            // u->son[++u->cnt] = v->son[i + 1];
            u->son[u->cnt + i + 1] = v->son[i + 1];
            v->son[i + 1]->fa = u, v->son[i + 1] = NULL;
        }
        u->val = mergelist(u->val, v->val);
        v->cnt = 0;
    }
    delete_right_by_id(fa, id); // what if this sentence is put in front of if (u->t == LEAF) sentence?
    pushup(u);
}
template <typename T> void BPlusTree<T>::fix(Node<T> *u){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    if (!fa) return;
    if (id > 0 && fa->son[id - 1]->cnt > m){ // borrow pre
        Node<T> *v = fa->son[id - 1];
        Node<T> *s = (u->t == LEAF) ? NULL : v->son[v->cnt];
        Value<T> *pre = (u->t == LEAF) ? (*v->val)[v->cnt - 1]->key : (*fa->val)[id - 1]->key;
        if (u->t == INTERNAL) (*fa->val)[id - 1]->key = (*v->val)[v->cnt - 1]->key; // change parent
        insert_left_by_id(u, 0, s, pre);
        delete_right_by_id(v, v->cnt - 1);
        pushup(u), pushup(v);
    }else if (id < fa->cnt && fa->son[id + 1]->cnt > m){ // borrow nxt
        Node<T> *v = fa->son[id + 1];
        Node<T> *s = (u->t == LEAF) ? NULL : v->son[0];
        Value<T> *nxt = (u->t == LEAF) ? (*v->val)[0]->key : (*fa->val)[id]->key;
        if (u->t == INTERNAL) (*fa->val)[id]->key = (*v->val)[0]->key; // change parent
        delete_left_by_id(v, 0);               
        insert_right_by_id(u, u->cnt, s, nxt); 
        pushup(u), pushup(v);
    }else{
        if (id > 0) merge(fa->son[id - 1], u);
        else merge(u, fa->son[id + 1]);
    }
}
template <typename T> void BPlusTree<T>::erase(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < (*u->val)[i]->key->value) break;
        else if (u->t == LEAF && val <= (*u->val)[i]->key->value) break;
    }
    Value<T> *deleted_value = NULL;
    if (u->t == INTERNAL) erase(u->son[i], val);
    else{
        if (i >= u->cnt || (*u->val)[i]->key->value != val) return; // not found
        if ((*u->val)[i]->key->count > 1){
            --(*u->val)[i]->key->count, pushup(u);
            return;
        }
        deleted_value = delete_right_by_id(u, i);
        delete deleted_value, deleted_value = nullptr;
    }
    if (u == root && !u->cnt){
        root = u->son[0];
        if(root) root->fa = NULL, pushup(root);
        delete u, u = nullptr;
        return;
    }
    if (u->cnt < m) fix(u);
    pushup(u);
}
template <typename T> int BPlusTree<T>::getrank(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < (*u->val)[i]->key->value) break;
        else if (u->t == LEAF && val <= (*u->val)[i]->key->value) break;
    }
    if (u->t == INTERNAL){
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->son[j]->sz;
        return rank + getrank(u->son[i], val);
    }else{
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += (*u->val)[j]->key->count;
        return rank + 1;
    }
}
template <typename T> T BPlusTree<T>::getval(Node<T> *u, int rank){
    int i = 0;
    if (u->t == INTERNAL){
        for (; i <= u->cnt; ++i){
            if (rank <= u->son[i]->sz) break;
            else rank -= u->son[i]->sz;
        }
        return getval(u->son[i], rank);
    }else{
        for (; i < u->cnt; ++i){
            if (rank >= 1 && rank <= (*u->val)[i]->key->count) return (*u->val)[i]->key->value;
            else rank -= (*u->val)[i]->key->count;
        }
    }
}
template <typename T> int BPlusTree<T>::getpre(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < (*u->val)[i]->key->value) break;
        else if (u->t == LEAF && val <= (*u->val)[i]->key->value) break;
    }
    if (u->t == INTERNAL) return getpre(u->son[i], val);
    else{
        if (i == 0) u = u->pre, i = u->cnt;
        assert(u != NULL);
        return (*u->val)[i - 1]->key->value;
    }
}
template <typename T>int BPlusTree<T>::getnxt(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i)
        if (val < (*u->val)[i]->key->value) break;
    if (u->t == INTERNAL) return getnxt(u->son[i], val);
    else{
        if (i == u->cnt) u = u->nxt, i = 0;
        assert(u != NULL);
        return (*u->val)[i]->key->value;
    }
}
void solve(){
    scanf("%d", &n);
    BPlusTree<int> *S = new BPlusTree<int>();
    int tt = 0;
    for (int i = 1; i <= n; ++i){
        int op, x;
        scanf("%d%d", &op, &x);
        if (op == 1){
            S->insert(S->root, x);
        }else if (op == 2){
            S->erase(S->root, x);
        }else if (op == 3){
            printf("%d\n", S->getrank(S->root, x));
        }else if (op == 4){
            printf("%d\n", S->getval(S->root, x));
        }else if (op == 5){
            printf("%d\n", S->getpre(S->root, x));
        }else if (op == 6){
            printf("%d\n", S->getnxt(S->root, x));
        }
    }   
    delete S;
}
int main(){
    solve();
    return 0;
}

这份代码会分别出现 WA, RE 等问题

主要问题

1. 在 merge 合并跳表删除整个跳表和 B+ 树删除节点时, 同一个跳表会被删除两次

   delete v, v = nullptr; // note that this also delete v->val
   

   这会导致 RE

   同理, 在 split 中应该将原本新创建 v 而创建的 v->val 对象删除, 才能保证内存无泄露

2. 在 merge 里没有及时更新 u->cnt, v->cnt

3. 注意这个写法: (*u->val)[i], 等价于原本的 u->val[i], 这里因为 u->val 变成了跳表对象, 是一个指针, 所以需要先解引用, 再调用 SkipList 类的 operator []

4. 注意这句话:

   // Value<T> *deleted_val = ((*u->val)[id]) ? (*u->val)[id]->key : NULL;
   Value<T> *deleted_val = (*u->val)[id]->key;
   

   特判 (*u->val)[id] 是否存在是有必要的

5. 注意 delete_left/right_by_id 中的这句话:

   u->val->erase(deleted_val);
   

   由于上面的问题, deleted_val 可能为 NULL, 而在跳表中无法通过比较键值的方式找到这个 NULL, 所以这种写法只能遍历整个跳表找 NULL

   将 erase 函数改成:

   if(!key){
       SLNode<T> *q = p;
       int rank = 0;
       while(q && q->forward[0]->key != NULL) q = q->forward[0], ++rank;
       q = q->forward[0], ++rank;
       for (int i = level; i >= 0; --i){
           while (p->forward[i] != NULL && now + p->next[i] < rank)
               now += p->next[i], p = p->forward[i];
           update[i] = p;
           pos[i] = now;
       }
       p = p->forward[0], now++;
   }else{
       for (int i = level; i >= 0; --i){
           while (p->forward[i] != NULL && p->forward[i]->key->value < key->value)
               now += p->next[i], p = p->forward[i];
           update[i] = p;
           pos[i] = now;
       }
       p = p->forward[0], now++;
       if (!p || p->key->value != key->value)
           return false;
   }
   

6. 注意这个特判:

   // if (u->t == LEAF && id == 0){
   //     SLNode<T> *p = (*u->val)[0];
   //     if(p != NULL) change_parent(u, deleted_val, p->value); // note this sepcial judge
   //     else change_parent(u, deleted_val, NULL);
   // }
   if (u->t == LEAF && id == 0) change_parent(u, deleted_val, p->value);
   

   不能直接 p->value, p 可能为空, 因为 u->val 可能已经被删空

   同理在 insert_left/right_by_id 中:

   // else if (id == 0){   
   //     SLNode<T> *p = (*u->val)[0];
   //     if(p != NULL) change_parent(u, p->value, val);
   //     else change_parent(u, NULL, val);
   // }
   else if (id == 0) change_parent(u, p->value, val);
   

   也要做同样修改

跳表版本, 无内存泄露, 但运行巨慢

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8 + 10;
int n, valcnt, o, m, ccnt;
const int MAXL = 20;
const double p = 0.5;
template <typename T> struct Value{
    public:
    T value;
    int count;
    Value<T>(T value, int count) : value(value), count(count) {++valcnt;}
    Value<T>() {}
    ~Value<T>() {--valcnt;}
    bool operator <(const Value<T> &x) const{
        return value < x.value;
    }
};
template <typename T> class SkipList;
template <typename T> class SLNode{
public:
    SLNode<T> **forward;
    int *next;
    Value<T> *key;
    Value<T> *value;
    int level;
    SLNode<T>() {}
    ~SLNode<T>() {
        delete [] forward;
        delete [] next;
    }
    SLNode<T>(Value<T> * key, Value<T> * value) : key(key), value(value) {
        next = new int [MAXL + 1];
        forward = new SLNode<T> *[MAXL + 1]; 
        for (int i = 0; i <= MAXL; ++i)
            forward[i] = NULL, next[i] = 0;
        level = RandomLevel();
    }
    int RandomLevel(){
        int lv = 0;
        int maxn = 1023;
        while (lv < MAXL && rand() % maxn < (int)(p * maxn)) ++lv;
        return lv;
    }
    friend class SkipList<T>;
};
template <typename T> class SkipList {
public:
    static const int MAXL = 20, INF = 1e9 + 10;
    int level;
    int length;
    SLNode<T> *head;
    SkipList<T>() { head = new SLNode<T>(0, 0), level = 0, length = 0; }
    ~SkipList<T>() {
        SLNode<T> *p = head;
        while(p){
            SLNode<T> *q = p->forward[0];
            delete p, p = q;
        }   
    }
    SLNode<T>* operator [](int rank){ // from 0
        ++rank;
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->next[i] < rank)
                rank -= p->next[i], p = p->forward[i];
        }
        p = p->forward[0];
        return p;
    }
    int getrank(Value<T> * key){
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->key->value < key->value)
                now += p->next[i], p = p->forward[i];
        }
        return now + 1;
    }
    Value<T> * kth(int rank){
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->next[i] < rank)
                rank -= p->next[i], p = p->forward[i];
        }
        p = p->forward[0];
        return p->key;
    }
    Value<T> * pre(Value<T> * key){
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->key->value < key->value)
                p = p->forward[i];
        }
        return p->key;
    }
    Value<T> * nxt(Value<T> * key){
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->key->value <= key->value)
                p = p->forward[i];
        }
        p = p->forward[0];
        if(p) return p->key;
        return INF;
    }
    void insert(Value<T> * key, Value<T> * value){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->key->value < key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++; // now += p->next[0]
        SLNode<T> *NewNode = new SLNode<T>(key, value);
        if (level < NewNode->level){
            NewNode->level = head->level = ++level;
            update[level] = head, pos[level] = 0;
        }
        for (int i = 0; i <= level; ++i){
            p = update[i];
            if (i <= NewNode->level){
                NewNode->forward[i] = p->forward[i];
                if (p->forward[i]) NewNode->next[i] = p->next[i] - (now - pos[i]) + 1;
                else NewNode->next[i] = 0;
                p->next[i] = now - pos[i];
                p->forward[i] = NewNode;
            }else{
                if (p->forward[i]) p->next[i]++;
                else p->next[i] = 0;
            }
        }
        length++;
    }
    bool erase(Value<T> * key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        if(!key){ 
            // this part is trash, piece of shit! just don't know how to delete NULL from ordered list, I traverse the whole list to find NULL
            // here's an interesting fact: this case will appear at most once in every operation. Can you prove this theoretically?
            SLNode<T> *q = p;
            int rank = 0;
            while(q && q->forward[0]->key != NULL) q = q->forward[0], ++rank;
            q = q->forward[0], ++rank;
            for (int i = level; i >= 0; --i){
                while (p->forward[i] != NULL && now + p->next[i] < rank)
                    now += p->next[i], p = p->forward[i];
                update[i] = p;
                pos[i] = now;
            }
            p = p->forward[0], now++;
            ++ccnt;
        }else{
            for (int i = level; i >= 0; --i){
                while (p->forward[i] != NULL && p->forward[i]->key->value < key->value)
                    now += p->next[i], p = p->forward[i];
                update[i] = p;
                pos[i] = now;
            }
            p = p->forward[0], now++;
            if (!p || p->key->value != key->value)
                return false;
        }
        for (int i = 0; i <= level; ++i){
            if (update[i]->forward[i] != p){
                if (update[i]->forward[i]) update[i]->next[i]--;
                else update[i]->next[i] = 0;
            }else{
                update[i]->forward[i] = p->forward[i];
                update[i]->next[i] += p->next[i] - 1;
            }
        }
        delete p;
        while (level > 0 && head->forward[level] == NULL) level--;
        head->level = level;
        length--;
        return true;
    }
    void print(){
        SLNode<T> *p = head;
        while (p){
            cout << p->key << " ";
            if (p == head) cout << level << ": ";
            else cout << p->level << ": ";
            for (int i = level; i >= 0; --i){
                if (p->forward[i] == NULL) cout << "NULL ";
                else cout << "(" << p->forward[i]->key << ", " << p->next[i] << ") ";
            }
            cout << endl;
            p = p->forward[0];
        }
        cout << "length: " << length << endl;
    }
};
template <typename T> pair<SkipList<T>*, SkipList<T>*> splitlist(SkipList<T>* u, int rank){
    SkipList<T>* v = new SkipList<T>();
    SLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    SLNode<T> *p = u->head;
    int now = 0, level = u->level;
    for (int i = level; i >= 0; --i){
        while (p->forward[i] != NULL && now + p->next[i] < rank)
            now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    v->level = level, v->head->level = level;
    v->length = u->length - now + 1, u->length = now - 1;
    for (int i = 0; i <= level; ++i){
        p = update[i];
        v->head->forward[i] = p->forward[i];
        if (p->forward[i]) v->head->next[i] = p->next[i] - (now - pos[i]) + 1;
        else v->head->next[i] = 0;
        p->next[i] = 0;
        p->forward[i] = NULL;
    }
    return make_pair(u, v);
}
template <typename T> SkipList<T>* mergelist(SkipList<T>* u, SkipList<T>* v){
    SLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    SLNode<T> *p = u->head;
    int now = 0;
    for (int i = u->level; i >= 0; --i){
        while (p->forward[i] != NULL) now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    for (int i = 0; i <= v->level; ++i){
        if(i > u->level){
            u->head->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) u->head->next[i] = u->length + v->head->next[i];
            else u->head->next[i] = 0;
        }else{
            update[i]->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) update[i]->next[i] = (u->length - pos[i]) + v->head->next[i];
            else update[i]->next[i] = 0;
        }
        v->head->forward[i] = NULL;
    }
    u->level = max(u->level, v->level);
    u->head->level = u->level;
    u->length += v->length;
    // delete v; // v will be deleted in B+ tree (when Node is deleted, Node->Value will also be deleted)
    return u;
}
enum type {INTERNAL, LEAF};
template <typename T> class Node{
public:
    static const int M = 3, m = (M - 1) / 2;
    Node<T> *fa, *nxt, *pre;
    SkipList<T> *val;
    Node<T> **son;
    int cnt, sz; // cnt: num of val, <= M - 1; when >= M, split
    type t;
    Node<T>(type t, Node<T> *fa) : t(t), fa(fa){
        nxt = pre = NULL, cnt = sz = 0;
        val = new SkipList<T>();
        son = (Node<T> **)malloc(sizeof(Node<T> *) * (M + 1));
        for (int i = 0; i <= M; ++i) son[i] = NULL;
    }
    Node<T>() {}
    ~Node<T>() {
        delete [] son; // add this line will cause luogu P3369 RE
        delete val;
    }
};
template <typename T> class BPlusTree{
public:
    static const int M = 3, m = (M - 1) / 2;
private:
    void insert_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val);
    void insert_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val);
    Value<T>* delete_left_by_id(Node<T> *u, int id);
    Value<T>* delete_right_by_id(Node<T> *u, int id);
    void linkin(Node<T> *u, Node<T> *v);
    void linkout(Node<T> *u, Node<T> *v);
    void split(Node<T> *u);
    void pushup(Node<T> *u);
    void merge(Node<T> *u, Node<T> *v);
    void change_parent(Node<T> *u, Value<T> *pre, Value<T> *now);
    void fix(Node<T> *u);
    int get_id(Node<T> *u);
    void clear(Node<T> *u){
        if(!u) return;
        for(int i = 0; i <= u->cnt; ++i){
            clear(u->son[i]);
        }
        delete u, u = nullptr;
    }
    void destroy(Node<T> *u){
        while(u && u->t == INTERNAL) u = u->son[0];
        while(u){
            for(int i = 0; i < u->cnt; ++i){
                delete (*u->val)[i]->key, (*u->val)[i]->key = nullptr;
            }
            u = u->nxt;
        }
    }
public:
    Node<T> *root;
    void insert(Node<T> *u, T val);
    void erase(Node<T> *u, T val);
    int getrank(Node<T> *x, T val);
    T getval(Node<T> *x, int rank);
    int getpre(Node<T> *x, T val);
    int getnxt(Node<T> *x, T val);
    BPlusTree<T>() { root = NULL; }
    ~BPlusTree<T>() { 
        destroy(root); 
        clear(root); 
    }
    void dfs(Node<T> *x) {assert(x!=NULL);cerr<<x<<"(type="<<(x->t==LEAF?"LEAF":"INTERNAL")<<",id="<<get_id(x)<<",sz="<<x->sz<<")->[";SLNode<T> *p = x->val->head->forward[0];while(p){if(p->key) cerr << p->key->value << " ";else cerr << "NULL ";p = p->forward[0];}cerr<<"]\n";if(x->t==LEAF) return;for(int i=0; i<x->cnt+1; ++i) dfs(x->son[i]);}
    // don't mind this long shit, it's just a printing function(
};
template <typename T> int BPlusTree<T>::get_id(Node<T> *u){
    Node<T> *fa = u->fa;
    if (!fa) return 0;
    for (int i = 0; i <= fa->cnt; ++i) 
        if (fa->son[i] == u) return i;
}
template <typename T> void BPlusTree<T>::linkin(Node<T> *u, Node<T> *v){
    Node<T> *nxt = u->nxt; // double linked list, insert v
    v->nxt = u->nxt, v->pre = u, u->nxt = v;
    if(nxt) nxt->pre = v;
}
template <typename T> void BPlusTree<T>::linkout(Node<T> *u, Node<T> *v){
    Node<T> *nxt = v->nxt; // double linked list, delete v
    u->nxt = nxt, v->nxt = NULL, v->pre = NULL;
    if (nxt) nxt->pre = u;
}
template <typename T> void BPlusTree<T>::pushup(Node<T> *u){
    if(!u) return;
    u->sz = 0;
    if (u->t == LEAF){
        for (int i = 0; i < u->cnt; ++i) u->sz += (*u->val)[i]->key->count;
    }else{
        for (int i = 0; i <= u->cnt; ++i) u->sz += u->son[i]->sz;
    }
}
template <typename T> void BPlusTree<T>::change_parent(Node<T> *u, Value<T> *pre, Value<T> *now){
    u = u->fa;
    if (pre == now) return;
    for(; u; u = u->fa){ // INTERNAL
        for (int i = u->cnt - 1; i >= 0; --i){
            if ((*u->val)[i] == pre){
                (*u->val)[i] = now;
                return;
            }
        }
    }
}
template <typename T> void BPlusTree<T>::insert_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val){ 
    // insert val[id] and son[id]
    for (int i = u->cnt; i >= id; --i) u->son[i + 1] = u->son[i];
    if (u->t == INTERNAL) u->son[id] = s, s->fa = u;
    else if (id == 0){
        SLNode<T> *p = (*u->val)[0];
        if(p != NULL) change_parent(u, p->value, val);
        else change_parent(u, NULL, val); // note this 
    }
    u->val->insert(val, val);
    ++u->cnt, pushup(u);
}
template <typename T> void BPlusTree<T>::insert_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> *val){ 
    // insert val[id] and son[id + 1]
    for (int i = u->cnt; i >= id + 1; --i) u->son[i + 1] = u->son[i];
    if (u->t == INTERNAL) u->son[id + 1] = s, s->fa = u;   
    else if (id == 0){   
        SLNode<T> *p = (*u->val)[0];
        if(p != NULL) change_parent(u, p->value, val);
        else change_parent(u, NULL, val);
    }
    u->val->insert(val, val);
    ++u->cnt, pushup(u);
}
template <typename T> Value<T>* BPlusTree<T>::delete_left_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id]
    Value<T> *deleted_val = ((*u->val)[id]) ? (*u->val)[id]->key : NULL;
    for (int i = id + 1; i <= u->cnt; ++i) u->son[i - 1] = u->son[i];
    u->val->erase(deleted_val);
    u->son[u->cnt] = NULL;
    if (u->t == LEAF && id == 0){
        SLNode<T> *p = (*u->val)[0];
        if(p != NULL) change_parent(u, deleted_val, p->value);
        else change_parent(u, deleted_val, NULL);
    }
    u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> Value<T>* BPlusTree<T>::delete_right_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id + 1]
    Value<T> *deleted_val = ((*u->val)[id]) ? (*u->val)[id]->key : NULL;
    for (int i = id + 1; i < u->cnt; ++i) u->son[i] = u->son[i + 1];
    u->son[u->cnt] = NULL;
    u->val->erase(deleted_val); // if deleted_val == NULL, then is O(M), otherwise O(log M)
    if (u->t == LEAF && id == 0){
        SLNode<T> *p = (*u->val)[0];
        if(p != NULL) change_parent(u, deleted_val, p->value); // note this sepcial judge
        else change_parent(u, deleted_val, NULL);
    }
    u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> void BPlusTree<T>::split(Node<T> *u){
    int mid = (u->t == LEAF) ? M / 2 : (M - 1) / 2;
    Node<T> *fa = u->fa;
    if (!fa) root = fa = new Node<T>(INTERNAL, NULL), fa->son[0] = u, u->fa = fa;
    Node<T> *v = new Node<T>(u->t, fa);
    int id = get_id(u);
    insert_right_by_id(fa, id, v, (*u->val)[mid]->key);
    if (u->t == LEAF){
        pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, mid + 1);
        u->val = p.first;
        delete v->val, v->val = p.second;
        u->cnt = mid, v->cnt = M - mid;
        linkin(u, v);
    }else{
        for (int i = mid + 1; i <= u->cnt; ++i){
            v->son[i - mid - 1] = u->son[i];
            u->son[i]->fa = v, u->son[i] = NULL;
        }
        pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, mid + 1);
        u->val = p.first;
        pair<SkipList<T>*, SkipList<T>* > q = splitlist(p.second, 2);
        delete q.first;
        delete v->val, v->val = q.second;
        u->cnt = mid, v->cnt = M - mid - 1;
    }
    pushup(u), pushup(v);
}
template <typename T> void BPlusTree<T>::insert(Node<T> *u, T val){
    if (!root){
        root = new Node<T>(LEAF, NULL);
        insert_right_by_id(root, 0, NULL, new Value<T>(val, 1));
        pushup(root);
        return;
    }
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < (*u->val)[i]->key->value) break;
        else if (u->t == LEAF && val <= (*u->val)[i]->key->value) break;
    }
    if (u->t == INTERNAL) insert(u->son[i], val);
    else{
        if (i < u->cnt && val == (*u->val)[i]->key->value){
            ++(*u->val)[i]->key->count, pushup(u);
            return;
        }
        insert_right_by_id(u, i, NULL, new Value<T>(val, 1));
    }
    if (u->cnt >= M) split(u);
    pushup(u);
}
template <typename T> void BPlusTree<T>::merge(Node<T> *u, Node<T> *v){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    Value<T> *val = (*fa->val)[id]->key;
    if (u->t == LEAF){
        if (!u->cnt) change_parent(u, NULL, (*v->val)[0]->key); // always change parent when i == 0 and LEAF
        u->val = mergelist(u->val, v->val);
        u->cnt += v->cnt, v->cnt = 0;
        linkout(u, v);
    }else{
        insert_right_by_id(u, u->cnt, v->son[0], val);
        for (int i = 0; i < v->cnt; ++i){
            u->son[++u->cnt] = v->son[i + 1];
            v->son[i + 1]->fa = u, v->son[i + 1] = NULL;
        }
        u->val = mergelist(u->val, v->val);
        v->cnt = 0;
    }
    delete_right_by_id(fa, id); // what if this sentence is put in front of if (u->t == LEAF) sentence?
    delete v, v = nullptr;// note that this also delete v->val
    pushup(u);
}
template <typename T> void BPlusTree<T>::fix(Node<T> *u){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    if (!fa) return;
    if (id > 0 && fa->son[id - 1]->cnt > m){ // borrow pre
        Node<T> *v = fa->son[id - 1];
        Node<T> *s = (u->t == LEAF) ? NULL : v->son[v->cnt];
        Value<T> *pre = (u->t == LEAF) ? (*v->val)[v->cnt - 1]->key : (*fa->val)[id - 1]->key;
        if (u->t == INTERNAL) (*fa->val)[id - 1]->key = (*v->val)[v->cnt - 1]->key; // change parent
        insert_left_by_id(u, 0, s, pre);
        delete_right_by_id(v, v->cnt - 1);
        pushup(u), pushup(v);
    }else if (id < fa->cnt && fa->son[id + 1]->cnt > m){ // borrow nxt
        Node<T> *v = fa->son[id + 1];
        Node<T> *s = (u->t == LEAF) ? NULL : v->son[0];
        Value<T> *nxt = (u->t == LEAF) ? (*v->val)[0]->key : (*fa->val)[id]->key;
        if (u->t == INTERNAL) (*fa->val)[id]->key = (*v->val)[0]->key; // change parent
        delete_left_by_id(v, 0);               
        insert_right_by_id(u, u->cnt, s, nxt); 
        pushup(u), pushup(v);
    }else{
        if (id > 0) merge(fa->son[id - 1], u);
        else merge(u, fa->son[id + 1]);
    }
}
template <typename T> void BPlusTree<T>::erase(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < (*u->val)[i]->key->value) break;
        else if (u->t == LEAF && val <= (*u->val)[i]->key->value) break;
    }
    Value<T> *deleted_value = NULL;
    if (u->t == INTERNAL) erase(u->son[i], val);
    else{
        if (i >= u->cnt || (*u->val)[i]->key->value != val) return; // not found
        if ((*u->val)[i]->key->count > 1){
            --(*u->val)[i]->key->count, pushup(u);
            return;
        }
        deleted_value = delete_right_by_id(u, i);
        delete deleted_value, deleted_value = nullptr;
    }
    if (u == root && !u->cnt){
        root = u->son[0];
        if(root) root->fa = NULL, pushup(root);
        delete u, u = nullptr;
        return;
    }
    if (u->cnt < m) fix(u);
    pushup(u);
}
template <typename T> int BPlusTree<T>::getrank(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < (*u->val)[i]->key->value) break;
        else if (u->t == LEAF && val <= (*u->val)[i]->key->value) break;
    }
    if (u->t == INTERNAL){
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->son[j]->sz;
        return rank + getrank(u->son[i], val);
    }else{
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += (*u->val)[j]->key->count;
        return rank + 1;
    }
}
template <typename T> T BPlusTree<T>::getval(Node<T> *u, int rank){
    int i = 0;
    if (u->t == INTERNAL){
        for (; i <= u->cnt; ++i){
            if (rank <= u->son[i]->sz) break;
            else rank -= u->son[i]->sz;
        }
        return getval(u->son[i], rank);
    }else{
        for (; i < u->cnt; ++i){
            if (rank >= 1 && rank <= (*u->val)[i]->key->count) return (*u->val)[i]->key->value;
            else rank -= (*u->val)[i]->key->count;
        }
    }
}
template <typename T> int BPlusTree<T>::getpre(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (val < (*u->val)[i]->key->value) break;
        else if (u->t == LEAF && val <= (*u->val)[i]->key->value) break;
    }
    if (u->t == INTERNAL) return getpre(u->son[i], val);
    else{
        if (i == 0) u = u->pre, i = u->cnt;
        assert(u != NULL);
        return (*u->val)[i - 1]->key->value;
    }
}
template <typename T>int BPlusTree<T>::getnxt(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i)
        if (val < (*u->val)[i]->key->value) break;
    if (u->t == INTERNAL) return getnxt(u->son[i], val);
    else{
        if (i == u->cnt) u = u->nxt, i = 0;
        assert(u != NULL);
        return (*u->val)[i]->key->value;
    }
}
void solve(){
    scanf("%d", &n);
    BPlusTree<int> *S = new BPlusTree<int>();
    int tt = 0;
    for (int i = 1; i <= n; ++i){
        int op, x;
        scanf("%d%d", &op, &x);
        //int tmp = ccnt;
        if (op == 1){
            S->insert(S->root, x);
        }else if (op == 2){
            S->erase(S->root, x);
        }else if (op == 3){
            printf("%d\n", S->getrank(S->root, x));
        }else if (op == 4){
            printf("%d\n", S->getval(S->root, x));
        }else if (op == 5){
            printf("%d\n", S->getpre(S->root, x));
        }else if (op == 6){
            printf("%d\n", S->getnxt(S->root, x));
        }
        //if(ccnt > tmp) cerr << ccnt - tmp << endl;
    }   
    delete S;
    //cerr<<ccnt<<endl;
}
int main(){
    solve();
    return 0;
}

这段代码本地运行 AC 并且无内存泄露, 但 luogu P3369: RE

同时运行时间很慢 P3369: 1.08s

主要问题

运行慢的原因是复杂度不对

1. 首先是单次 \(O(M)\) 的跳表删除 NULL 情况

   看起来总共的运行时间会是 \(O(M\log_MN)\), 但实际上这种情况最多发生一次, 就是叶子节点的唯一一个 Value 被删除时. 之后在合并叶子节点时需要删除内部节点的这个 NULL, 发生一次

   但这样复杂度就成了 \(O(M+\log N)\), 与 \(M\) 有关了

   如果不想要这个 \(O(M)\), 就需要特判删除时将叶子节点删空的情况, 避免内部节点出现在 delete_right_by_id 时被 change_parent 换成 NULL

2. 对于 pushup 函数:

   if (u->t == LEAF){
       for (int i = 0; i < u->cnt; ++i) u->sz += (*u->val)[i]->leaf_key->count;
   }else{
       for (int i = 0; i <= u->cnt; ++i) u->sz += u->son[i]->sz;
   }
   

   这部分变成了 \(O(M\log N)\)

   由于这个函数是平衡树用来查询用的维护函数, 所以直接删掉就行(

3. 对于 get_id 函数:

   for (int i = 0; i <= fa->cnt; ++i) 
   if (fa->son[i] == u) return i;
   

   这部分是 \(O(M)\) 的, 需要把 son 改成跳表维护, 变成 \(O(\log M)\)

4. 对于 change_parent 函数:

       for(; u; u = u->fa){ // INTERNAL
           for (int i = u->cnt - 1; i >= 0; --i){
               if ((*u->val)[i]->key == pre){
                   (*u->val)[i]->key = now;
                   return;
               }
           }
       }
   

   这部分复杂度是单次 \(O(M\log N)\) 的

   并且由于有 NULL 存在, 很难改成使用跳表 \(O(\log M)\) 查询 (跳表必须有序, 但 NULL 没法排序从而出现 RE), 所以很难优化到 \(O(\log N)\)

   要解决这个也和第一条类似, 避免内部节点出现 NULL

5. 其次是所有操作里的这个部分:

   int i = 0;
   for (; i < u->cnt; ++i){
       if (val < (*u->val)[i]->key->value) break;
       else if (u->t == LEAF && val <= (*u->val)[i]->key->value) break;
   }
   

   这会让复杂度直接变成 \(O(M\log M \times \frac{\log N}{\log M}) = O(M\log N)\)

   可以通过改成跳表查找, 变成 \(O(\log M\times \frac{\log N}{\log M})=O(\log N)\)

6. 最后是对于 son 的修改

   在插入删除中都会有 \(O(M)\) 的修改 son 的情况, 所以复杂度还是退回到 \(O(M\log_MN)\)

   注意由于我们要维护 son 的 fa 信息来支持 B+ 树的 merge, fix 操作中的找父亲操作, 所以这部分很难优化成 \(O(\log N)\) 了

   要想改成 \(O(\log N)\), 就需要调整几乎所有函数, 使得从父亲访问儿子, 而不从儿子访问父亲, 这样就可以避免使用 fa, 同时就可以把 son 改成用跳表维护, 复杂度就对了

后面会再改, 这份代码就仅供娱乐罢

另一种实现思路的 B+ 树

主要改了 Value 的存储方式:

Value<T> **leaf_val;
Value<T> ***internal_val;

分成 internal_val 和 leaf_val 两个指针数组存储值对象, 如果是叶子直接存值, 如果是内部节点, 则存储一个指向叶子节点 leaf_val 的指针

也就是说 internal_val 是三级指针

这样的好处是, 不再需要 change_parent 函数来对指向 Value 对象的指针进行更改, 现在内部节点的值元素指向叶子节点的值数组, 通过访问数组第 \(0\) 位可以自动获取需要的 Value 值

注意

这份代码在我的电脑上跑没问题(AC + 无内存泄露), 而 luogu P3369: RE

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8 + 10;
int n, valcnt, ccnt;
template <typename T> class Node;
enum type {INTERNAL, LEAF};
template <typename T> struct Value{
public:
    T value;
    int count;
    Value<T>(T value, int count) : value(value), count(count) {++valcnt;}
    Value<T>() {}
    ~Value<T>() {--valcnt;}
    bool operator<(const Value<T> &x) const{
        return value < x.value;
    }
};
template <typename T> class Node{
public:
    static const int M = 3, m = (M - 1) / 2;
    Node<T> *fa, *nxt, *pre;
    Node<T> **son;
    Value<T> **leaf_val;
    Value<T> ***internal_val;
    int cnt, sz; // cnt: num of val, <= M - 1; when >= M, split
    type t;
    Node<T>(type t, Node<T> *fa) : t(t), fa(fa){
        nxt = pre = NULL, cnt = sz = 0;
        leaf_val = NULL, internal_val = NULL;
        if(t == LEAF) leaf_val = new Value<T> * [M];
        else internal_val = new Value<T> **[M];
        son = new Node<T> * [M + 1];
        for (int i = 0; i <= M; ++i){
            if (i < M){
                if(t == LEAF) leaf_val[i] = NULL;
                else internal_val[i] = NULL;
            }
            son[i] = NULL;
        }
    }
    Node<T>() {}
    ~Node<T>() {delete [] son, delete [] leaf_val, delete [] internal_val; } // add this line will cause luogu P3369 RE
};
template <typename T> class BPlusTree{
public:
    static const int M = 3, m = (M - 1) / 2;
private:
    int traverse(Node<T> *u, T val);
    void insert_internal_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> **val);
    void insert_leaf_by_id(Node<T> *u, int id, Value<T> *val);
    void insert_internal_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> **val);
    Value<T>** delete_internal_right_by_id(Node<T> *u, int id);
    Value<T>* delete_leaf_by_id(Node<T> *u, int id);
    Value<T>** delete_internal_left_by_id(Node<T> *u, int id);
    void linkin(Node<T> *u, Node<T> *v);
    void linkout(Node<T> *u, Node<T> *v);
    void split(Node<T> *u);
    void pushup(Node<T> *u);
    void merge(Node<T> *u, Node<T> *v);
    void fix(Node<T> *u);
    int get_id(Node<T> *u);
    void clear(Node<T> *u){
        if(!u) return;
        for(int i = 0; i <= u->cnt; ++i) clear(u->son[i]);
        delete u, u = nullptr;
    }
    void destroy(Node<T> *u){
        while(u && u->t == INTERNAL) u = u->son[0];
        while(u){
            for(int i = 0; i < u->cnt; ++i)
                delete u->leaf_val[i], u->leaf_val[i] = nullptr;
            u = u->nxt;
        }
    }
public:
    Node<T> *root;
    void insert(Node<T> *u, T val);
    void erase(Node<T> *u, T val);
    int getrank(Node<T> *x, T val);
    T getval(Node<T> *x, int rank);
    int getpre(Node<T> *x, T val);
    int getnxt(Node<T> *x, T val);
    BPlusTree<T>() { root = NULL; }
    ~BPlusTree<T>() { 
        destroy(root); clear(root); 
    }
    void dfs(Node<T> *x) {assert(x!=NULL);cerr<<"(type="<<(x->t==LEAF?"LEAF":"INTERNAL");cerr<<",id="<<get_id(x)<<",sz="<<x->sz<<")->[";for(int i=0; i<x->cnt; ++i){if(!x->val[i]) cerr<<x->val[i]<<" ";else cerr<<x->val[i]->value<<" ";}cerr<<"]\n";if(x->t==LEAF) return;for(int i=0; i<x->cnt+1; ++i) dfs(x->son[i]);}
};
template <typename T> int BPlusTree<T>::get_id(Node<T> *u){
    Node<T> *fa = u->fa;
    if (!fa) return 0;
    for (int i = 0; i <= fa->cnt; ++i) 
        if (fa->son[i] == u) return i;
}
template <typename T> void BPlusTree<T>::linkin(Node<T> *u, Node<T> *v){
    Node<T> *nxt = u->nxt; // double linked list, insert v
    v->nxt = u->nxt, v->pre = u, u->nxt = v;
    if(nxt) nxt->pre = v;
}
template <typename T> void BPlusTree<T>::linkout(Node<T> *u, Node<T> *v){
    Node<T> *nxt = v->nxt; // double linked list, delete v
    u->nxt = nxt, v->nxt = NULL, v->pre = NULL;
    if (nxt) nxt->pre = u;
}
template <typename T> void BPlusTree<T>::pushup(Node<T> *u){
    if(!u) return;
    u->sz = 0;
    if (u->t == LEAF){
        for (int i = 0; i < u->cnt; ++i) u->sz += u->leaf_val[i]->count;
    }else{
        for (int i = 0; i <= u->cnt; ++i) u->sz += u->son[i]->sz;
    }
}
template <typename T> void BPlusTree<T>::insert_internal_right_by_id(Node<T> *u, int id, Node<T> *s, Value<T> **val){ 
    // insert val[id] and son[id + 1]
    for (int i = u->cnt; i >= id + 1; --i)
        u->internal_val[i] = u->internal_val[i - 1], u->son[i + 1] = u->son[i];
    u->son[id + 1] = s, s->fa = u, u->internal_val[id] = val;
    ++u->cnt, pushup(u);
}
template <typename T> void BPlusTree<T>::insert_leaf_by_id(Node<T> *u, int id, Value<T> *val){ 
    // insert val[id]
    for (int i = u->cnt; i >= id + 1; --i) u->leaf_val[i] = u->leaf_val[i - 1];
    u->leaf_val[id] = val;
    ++u->cnt, pushup(u);
}
template <typename T> void BPlusTree<T>::insert_internal_left_by_id(Node<T> *u, int id, Node<T> *s, Value<T> **val){ 
    // insert val[id] and son[id]
    for (int i = u->cnt; i >= id; --i){ 
        if (i >= 1) u->internal_val[i] = u->internal_val[i - 1];
        u->son[i + 1] = u->son[i];
    }
    u->son[id] = s, s->fa = u, u->internal_val[id] = val;
    ++u->cnt, pushup(u);
}
template <typename T> Value<T>* BPlusTree<T>::delete_leaf_by_id(Node<T> *u, int id){ 
    // delete val[id]
    Value<T> *deleted_val = u->leaf_val[id];
    for (int i = id + 1; i < u->cnt; ++i) u->leaf_val[i - 1] = u->leaf_val[i];
    u->leaf_val[u->cnt - 1] = NULL, u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> Value<T>** BPlusTree<T>::delete_internal_right_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id + 1]
    Value<T> **deleted_val = u->internal_val[id];
    for (int i = id + 1; i < u->cnt; ++i) 
        u->internal_val[i - 1] = u->internal_val[i], u->son[i] = u->son[i + 1];
    u->internal_val[u->cnt - 1] = NULL, u->son[u->cnt] = NULL;
    u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> Value<T>** BPlusTree<T>::delete_internal_left_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id]
    Value<T> **deleted_val = u->internal_val[id];
    for (int i = id + 1; i <= u->cnt; ++i){
        if(i < u->cnt) u->internal_val[i - 1] = u->internal_val[i];
        u->son[i - 1] = u->son[i];
    }
    u->internal_val[u->cnt - 1] = NULL, u->son[u->cnt] = NULL;
    u->cnt--, pushup(u);
    return deleted_val;
}
template<typename T> int BPlusTree<T>::traverse(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if (u->t == LEAF && val <= u->leaf_val[i]->value) break;
        else if (u->t == INTERNAL && val < u->internal_val[i][0]->value) break;
    }
    return i;
}
template <typename T> void BPlusTree<T>::split(Node<T> *u){
    int mid = (u->t == LEAF) ? M / 2 : (M - 1) / 2;
    Node<T> *fa = u->fa;
    if (!fa) root = fa = new Node<T>(INTERNAL, NULL), fa->son[0] = u, u->fa = fa;
    Node<T> *v = new Node<T>(u->t, fa);
    int id = get_id(u);
    Value<T> **p = (u->t == LEAF ? v->leaf_val : u->internal_val[mid]);
    insert_internal_right_by_id(fa, id, v, p);
    if (u->t == LEAF){
        for (int i = mid; i < u->cnt; ++i) v->leaf_val[i - mid] = u->leaf_val[i], u->leaf_val[i] = NULL;
        u->cnt = mid, v->cnt = M - mid;
        linkin(u, v);
    }else{
        for (int i = mid + 1; i <= u->cnt; ++i){
            if (i < u->cnt) v->internal_val[i - mid - 1] = u->internal_val[i], u->internal_val[i] = NULL;
            v->son[i - mid - 1] = u->son[i], u->son[i]->fa = v, u->son[i] = NULL;
        }
        u->cnt = mid, v->cnt = M - mid - 1;
    }
    pushup(u), pushup(v);
}
template <typename T> void BPlusTree<T>::insert(Node<T> *u, T val){
    if (!root){
        root = new Node<T>(LEAF, NULL);
        insert_leaf_by_id(root, 0, new Value<T>(val, 1));
        pushup(root);
        return;
    }
    int i = traverse(u, val);
    if (u->t == INTERNAL) insert(u->son[i], val);
    else{
        if (i < u->cnt && val == u->leaf_val[i]->value){
            ++u->leaf_val[i]->count, pushup(u);
            return;
        }
        insert_leaf_by_id(u, i, new Value<T>(val, 1));
    }
    if (u->cnt >= M) split(u);
    pushup(u);
}
template <typename T> void BPlusTree<T>::merge(Node<T> *u, Node<T> *v){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    if (u->t == LEAF){
        for (int i = 0; i < v->cnt; ++i)
            u->leaf_val[u->cnt++] = v->leaf_val[i], v->leaf_val[i] = NULL;
        v->cnt = 0;
        linkout(u, v);
    }else{
        insert_internal_right_by_id(u, u->cnt, v->son[0], fa->internal_val[id]);
        for (int i = 0; i < v->cnt; ++i){
            u->internal_val[u->cnt++] = v->internal_val[i], v->internal_val[i] = NULL;
            u->son[u->cnt] = v->son[i + 1], v->son[i + 1]->fa = u, v->son[i + 1] = NULL;
        }
        v->cnt = 0;
    }
    delete_internal_right_by_id(fa, id); // what if this sentence is put in front of if (u->t == LEAF) sentence?
    delete v, v = nullptr;
    pushup(u);
}
template <typename T> void BPlusTree<T>::fix(Node<T> *u){
    Node<T> *fa = u->fa;
    int id = get_id(u);
    if (!fa) return;
    if (id > 0 && fa->son[id - 1]->cnt > m){ // borrow pre
        Node<T> *v = fa->son[id - 1];
        if(u->t == LEAF){
            Value<T> *pre = v->leaf_val[v->cnt - 1];
            insert_leaf_by_id(u, 0, pre);
            delete_leaf_by_id(v, v->cnt - 1);
        }else{
            Node<T> *s = v->son[v->cnt];
            Value<T> **pre = fa->internal_val[id - 1];
            fa->internal_val[id - 1] = v->internal_val[v->cnt - 1]; // change parent
            insert_internal_left_by_id(u, 0, s, pre);
            delete_internal_right_by_id(v, v->cnt - 1);
        }
        pushup(u), pushup(v);
    }else if (id < fa->cnt && fa->son[id + 1]->cnt > m){ // borrow nxt
        Node<T> *v = fa->son[id + 1];
        if(u->t == LEAF){
            Value<T> *nxt = v->leaf_val[0];
            delete_leaf_by_id(v, 0);               
            insert_leaf_by_id(u, u->cnt, nxt); 
        }else{
            Node<T> *s = v->son[0];
            Value<T> **nxt = fa->internal_val[id];
            fa->internal_val[id] = v->internal_val[0]; // change parent
            delete_internal_left_by_id(v, 0);               
            insert_internal_right_by_id(u, u->cnt, s, nxt); 
        }
        pushup(u), pushup(v);
    }else{
        if (id > 0) merge(fa->son[id - 1], u);
        else merge(u, fa->son[id + 1]);
    }
}
template <typename T> void BPlusTree<T>::erase(Node<T> *u, T val){
    int i = traverse(u, val);
    if (u->t == INTERNAL) erase(u->son[i], val);
    else{
        if (i >= u->cnt || u->leaf_val[i]->value != val) return; // not found
        if (u->leaf_val[i]->count > 1){
            --u->leaf_val[i]->count, pushup(u);
            return;
        }
        Value<T> *deleted_value = delete_leaf_by_id(u, i);
        delete deleted_value, deleted_value = nullptr;
    }
    if (u == root && !u->cnt){
        root = u->son[0];
        if(root) root->fa = NULL, pushup(root);
        delete u, u = nullptr;
        return;
    }
    if (u->cnt < m) fix(u);
    pushup(u);
}
template <typename T> int BPlusTree<T>::getrank(Node<T> *u, T val){
    int i = traverse(u, val);
    if (u->t == INTERNAL){
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->son[j]->sz;
        return rank + getrank(u->son[i], val);
    }else{
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->leaf_val[j]->count;
        return rank + 1;
    }
}
template <typename T> T BPlusTree<T>::getval(Node<T> *u, int rank){
    int i = 0;
    if (u->t == INTERNAL){
        for (; i <= u->cnt; ++i){
            if (rank <= u->son[i]->sz) break;
            else rank -= u->son[i]->sz;
        }
        return getval(u->son[i], rank);
    }else{
        for (; i < u->cnt; ++i){
            if (rank >= 1 && rank <= u->leaf_val[i]->count) return u->leaf_val[i]->value;
            else rank -= u->leaf_val[i]->count;
        }
    }
}
template <typename T> int BPlusTree<T>::getpre(Node<T> *u, T val){
    int i = traverse(u, val);
    if (u->t == INTERNAL) return getpre(u->son[i], val);
    else{
        if (i == 0) u = u->pre, i = u->cnt;
        assert(u != NULL);
        return u->leaf_val[i - 1]->value;
    }
}
template <typename T>int BPlusTree<T>::getnxt(Node<T> *u, T val){
    int i = 0;
    for (; i < u->cnt; ++i){
        if(u->t == LEAF && val < u->leaf_val[i]->value) break;
        else if(u->t == INTERNAL && val < u->internal_val[i][0]->value) break;
    }
    if (u->t == INTERNAL) return getnxt(u->son[i], val);
    else{
        if (i == u->cnt) u = u->nxt, i = 0;
        assert(u != NULL);
        return u->leaf_val[i]->value;
    }
}
void solve(){
    scanf("%d", &n);
    BPlusTree<int> *S = new BPlusTree<int>();
    for (int i = 1; i <= n; ++i){
        int op, x;
        scanf("%d%d", &op, &x);
        int tmp = ccnt;
        if (op == 1){
            S->insert(S->root, x);
        }else if (op == 2){
            S->erase(S->root, x);
        }else if (op == 3){
            printf("%d\n", S->getrank(S->root, x));
        }else if (op == 4){
            printf("%d\n", S->getval(S->root, x));
        }else if (op == 5){
            printf("%d\n", S->getpre(S->root, x));
        }else if (op == 6){
            printf("%d\n", S->getnxt(S->root, x));
        }
    }
    delete S;
}
int main(){
    // for(int i=1;i<=1000;++i){
    //     freopen("P3369_10.in", "r", stdin);
    //     freopen("P3369_10.ans", "w", stdout);
    //     solve();
    // }
    solve();
    return 0;
}

上面 B+ 树的跳表实现

放一个 AC 的半成品, 还差 son 没有改成跳表, 其他都解决了

理论上, 现在可以解决之前跳表 B+ 树的所有问题, 得到复杂度正确的 B+ 树

一些发现

我写到一半, 发现就算是一部分改成了 \(O(\log N)\) 的复杂度, 速度依然被之前 \(O(M\log_MN)\) 的 B+ 树薄纱 (对于 \(M=10000, N=100000\), \(O(\log N)=\) 400ms, \(O(M\log_MN)=\) 196ms)

可能是因为面向对象编程, 创建 SkipList 对象次数太多, 删除次数太多, 导致速度变慢

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8 + 10;
const int MAXL = 20;
const double p = 0.5;
const int M = 1000, m = (M - 1) / 2;
int n, valcnt, ccnt, o;
template <typename T> class Node;
enum type {INTERNAL, LEAF};
template <typename T> struct Value{
public:
    T value;
    int count;
    Value<T>(T value, int count) : value(value), count(count) {++valcnt;}
    Value<T>() {}
    ~Value<T>() {--valcnt;}
    bool operator<(const Value<T> &x) const{
        return value < x.value;
    }
};
template <typename T> class SkipList;
template <typename T> class SLNode{
public:
    SLNode<T> **forward;
    int *next;
    Value<T> *leaf_key;
    SkipList<T> *internal_key;
    type t;
    int level;
    SLNode<T>() {}
    ~SLNode<T>() {
        delete [] forward;
        delete [] next;
    }
    SLNode<T>(Value<T> *leaf_key, SkipList<T> *internal_key, type t) : 
        leaf_key(leaf_key), internal_key(internal_key), t(t) {
        next = new int [MAXL + 1];
        forward = new SLNode<T> *[MAXL + 1]; 
        for (int i = 0; i <= MAXL; ++i)
            forward[i] = NULL, next[i] = 0;
        level = RandomLevel();
    }
    int RandomLevel(){
        int lv = 0;
        int maxn = 1023;
        while (lv < MAXL && rand() % maxn < (int)(p * maxn)) ++lv;
        return lv;
    }
    friend class SkipList<T>;
};
template <typename T> class SkipList {
public:
    int level;
    int length;
    type t;
    SLNode<T> *head;
    SkipList<T>(type t) :t(t) { head = new SLNode<T>(0, 0, t), level = 0, length = 0; }
    ~SkipList<T>() {
        SLNode<T> *p = head;
        while(p){
            SLNode<T> *q = p->forward[0];
            delete p, p = q;
        }   
    }
    SLNode<T>* operator [](int rank){ // from 0
        // speed up internal_key to O(1)
        if(rank == 0) return head->forward[0];
        ++rank;
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->next[i] < rank)
                rank -= p->next[i], p = p->forward[i];
        }
        p = p->forward[0];
        return p;
    }
    int getrank_leaf(T key){
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->leaf_key->value < key)
                now += p->next[i], p = p->forward[i];
        }
        return now + 1;
    }
    int getrank_Leaf(T key){
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->leaf_key->value <= key)
                now += p->next[i], p = p->forward[i];
        }
        return now + 1;
    }
    int getrank_internal(T key){
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && (*p->forward[i]->internal_key)[0]->leaf_key->value <= key)
                now += p->next[i], p = p->forward[i];
        }
        return now + 1;
    }
    void insert_leaf(Value<T> *key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->leaf_key->value < key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++; // now += p->next[0]
        SLNode<T> *NewNode = new SLNode<T>(key, NULL, t);
        if (level < NewNode->level){
            NewNode->level = head->level = ++level;
            update[level] = head, pos[level] = 0;
        }
        for (int i = 0; i <= level; ++i){
            p = update[i];
            if (i <= NewNode->level){
                NewNode->forward[i] = p->forward[i];
                if (p->forward[i]) NewNode->next[i] = p->next[i] - (now - pos[i]) + 1;
                else NewNode->next[i] = 0;
                p->next[i] = now - pos[i];
                p->forward[i] = NewNode;
            }else{
                if (p->forward[i]) p->next[i]++;
                else p->next[i] = 0;
            }
        }
        length++;
    }

    void insert_internal(SkipList<T> *key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && (*p->forward[i]->internal_key)[0]->leaf_key->value < (*key)[0]->leaf_key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++; // now += p->next[0]
        SLNode<T> *NewNode = new SLNode<T>(NULL, key, t);
        if (level < NewNode->level){
            NewNode->level = head->level = ++level;
            update[level] = head, pos[level] = 0;
        }
        for (int i = 0; i <= level; ++i){
            p = update[i];
            if (i <= NewNode->level){
                NewNode->forward[i] = p->forward[i];
                if (p->forward[i]) NewNode->next[i] = p->next[i] - (now - pos[i]) + 1;
                else NewNode->next[i] = 0;
                p->next[i] = now - pos[i];
                p->forward[i] = NewNode;
            }else{
                if (p->forward[i]) p->next[i]++;
                else p->next[i] = 0;
            }
        }
        length++;
    }


    bool erase_leaf(Value<T> *key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->leaf_key->value < key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++;
        if (!p || p->leaf_key->value != key->value)
            return false;

        for (int i = 0; i <= level; ++i){
            if (update[i]->forward[i] != p){
                if (update[i]->forward[i]) update[i]->next[i]--;
                else update[i]->next[i] = 0;
            }else{
                update[i]->forward[i] = p->forward[i];
                update[i]->next[i] += p->next[i] - 1;
            }
        }
        delete p;
        while (level > 0 && head->forward[level] == NULL) level--;
        head->level = level;
        length--;
        return true;
    }

    bool erase_internal(SkipList<T> *key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && (*p->forward[i]->internal_key)[0]->leaf_key->value < (*key)[0]->leaf_key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++;
        if (!p || (*p->internal_key)[0]->leaf_key->value != (*key)[0]->leaf_key->value)
            return false;

        for (int i = 0; i <= level; ++i){
            if (update[i]->forward[i] != p){
                if (update[i]->forward[i]) update[i]->next[i]--;
                else update[i]->next[i] = 0;
            }else{
                update[i]->forward[i] = p->forward[i];
                update[i]->next[i] += p->next[i] - 1;
            }
        }
        delete p;
        while (level > 0 && head->forward[level] == NULL) level--;
        head->level = level;
        length--;
        return true;
    }
    void print(){
        SLNode<T> *p = head;
        while (p){
            cout << p->key << " ";
            if (p == head) cout << level << ": ";
            else cout << p->level << ": ";
            for (int i = level; i >= 0; --i){
                if (p->forward[i] == NULL) cout << "NULL ";
                else cout << "(" << p->forward[i]->key << ", " << p->next[i] << ") ";
            }
            cout << endl;
            p = p->forward[0];
        }
        cout << "length: " << length << endl;
    }
};
template <typename T> pair<SkipList<T>*, SkipList<T>*> splitlist(SkipList<T>* u, int rank){
    SkipList<T>* v = new SkipList<T>(u->t);
    SLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    SLNode<T> *p = u->head;
    int now = 0, level = u->level;
    for (int i = level; i >= 0; --i){
        while (p->forward[i] != NULL && now + p->next[i] < rank)
            now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    v->level = level, v->head->level = level;
    v->length = u->length - now + 1, u->length = now - 1;
    for (int i = 0; i <= level; ++i){
        p = update[i];
        v->head->forward[i] = p->forward[i];
        if (p->forward[i]) v->head->next[i] = p->next[i] - (now - pos[i]) + 1;
        else v->head->next[i] = 0;
        p->next[i] = 0;
        p->forward[i] = NULL;
    }
    return make_pair(u, v);
}
template <typename T> SkipList<T>* mergelist(SkipList<T>* u, SkipList<T>* v){
    SLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    SLNode<T> *p = u->head;
    int now = 0;
    for (int i = u->level; i >= 0; --i){
        while (p->forward[i] != NULL) now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    for (int i = 0; i <= v->level; ++i){
        if(i > u->level){
            u->head->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) u->head->next[i] = u->length + v->head->next[i];
            else u->head->next[i] = 0;
        }else{
            update[i]->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) update[i]->next[i] = (u->length - pos[i]) + v->head->next[i];
            else update[i]->next[i] = 0;
        }
        v->head->forward[i] = NULL;
    }
    u->level = max(u->level, v->level);
    u->head->level = u->level;
    u->length += v->length;
    // delete v; // v will be deleted in B+ tree (when Node is deleted, Node->Value will also be deleted)
    return u;
}
template <typename T> class Node{
public:
    Node<T> *fa, *nxt, *pre;
    Node<T> **son;

    SkipList<T> *val;
    int cnt, sz; // cnt: num of val, <= M - 1; when >= M, split
    type t;
    Node<T>(type t, Node<T> *fa) : t(t), fa(fa){
        nxt = pre = NULL, cnt = sz = 0;
        val = new SkipList<T>(t);
        son = new Node<T> * [M + 1];
        for (int i = 0; i <= M; ++i) son[i] = NULL;
    }
    Node<T>() {}
    ~Node<T>() {delete [] son, delete val; } // add this line will cause luogu P3369 RE
};
template <typename T> class BPlusTree{
private:
    int traverse(Node<T> *u, T val);
    int Traverse(Node<T> *u, T val);
    void insert_internal_right_by_id(Node<T> *u, int id, Node<T> *s, SkipList<T> *val);
    void insert_leaf_by_id(Node<T> *u, int id, Value<T> *val);
    void insert_internal_left_by_id(Node<T> *u, int id, Node<T> *s, SkipList<T> *val);
    SkipList<T>* delete_internal_right_by_id(Node<T> *u, int id);
    Value<T>* delete_leaf_by_id(Node<T> *u, int id);
    SkipList<T>* delete_internal_left_by_id(Node<T> *u, int id);
    void linkin(Node<T> *u, Node<T> *v);
    void linkout(Node<T> *u, Node<T> *v);
    void split(Node<T> *u, Node<T> *fa);
    void pushup(Node<T> *u);
    void merge(Node<T> *u, Node<T> *v, Node<T> *fa);
    void fix(Node<T> *u, Node<T> *fa);
    int get_id(Node<T> *u, Node<T> *fa);
    void clear(Node<T> *u){
        if(!u) return;
        for(int i = 0; i <= u->cnt; ++i) clear(u->son[i]);
        delete u, u = nullptr;
    }
    void destroy(Node<T> *u){
        while(u && u->t == INTERNAL) u = u->son[0];
        while(u){
            for(int i = 0; i < u->cnt; ++i){
                delete (*u->val)[i]->leaf_key, (*u->val)[i]->leaf_key = nullptr;
            }
            u = u->nxt;
        }
    }
public:
    Node<T> *root;
    void insert(Node<T> *u, Node<T> *fa, T val);
    void erase(Node<T> *u, Node<T> *fa, T val);
    int getrank(Node<T> *x, T val);
    T getval(Node<T> *x, int rank);
    int getpre(Node<T> *x, T val);
    int getnxt(Node<T> *x, T val);
    BPlusTree<T>() { root = NULL; }
    ~BPlusTree<T>() { 
        destroy(root); clear(root); 
    }
    void dfs(Node<T> *x) {
        assert(x!=NULL);
        cerr<<x->val<<"(type="<<(x->t==LEAF?"LEAF":"INTERNAL");
        //cerr<<",id="<<get_id(x)<<",sz="<<x->sz;
        cerr<<")->[";
        SLNode<T> *p = x->val->head->forward[0];
        if(x->t == LEAF){
            while(p){
                if(p->leaf_key) cerr << p->leaf_key->value << " ";
                else cerr << "NULL ";
                p = p->forward[0];
            }
        }else{
            while(p){
                if((*p->internal_key)[0]) cerr << (*p->internal_key)[0]->leaf_key->value << " ";
                else cerr << "NULL ";
                p = p->forward[0];
            }
        }
        cerr<<"]\n";
        if(x->t==LEAF) return;
        for(int i=0; i<x->cnt+1; ++i) dfs(x->son[i]);
    }
};


template<typename T> int BPlusTree<T>::traverse(Node<T> *u, T val){
    int i = 0;
    if(u->t == LEAF) i = u->val->getrank_leaf(val) - 1;
    else i = u->val->getrank_internal(val) - 1;

    // for (; i < u->cnt; ++i){
    //     if (u->t == LEAF){
    //         if(val <= (*u->val)[i]->leaf_key->value) break;
    //     }
    //     else if (u->t == INTERNAL && val < (*(*u->val)[i]->internal_key)[0]->leaf_key->value) break;
    // }
    return i;
}
template<typename T> int BPlusTree<T>::Traverse(Node<T> *u, T val){
    int i = 0;
    if(u->t == LEAF) i = u->val->getrank_Leaf(val) - 1; // different
    else i = u->val->getrank_internal(val) - 1;
    return i;
}

template <typename T> int BPlusTree<T>::get_id(Node<T> *u, Node<T> *fa){
    // Node<T> *fa = u->fa;
    if (!fa) return 0;
    for (int i = 0; i <= fa->cnt; ++i) 
        if (fa->son[i] == u) return i;
}
template <typename T> void BPlusTree<T>::linkin(Node<T> *u, Node<T> *v){
    Node<T> *nxt = u->nxt; // double linked list, insert v
    v->nxt = u->nxt, v->pre = u, u->nxt = v;
    if(nxt) nxt->pre = v;
}
template <typename T> void BPlusTree<T>::linkout(Node<T> *u, Node<T> *v){
    Node<T> *nxt = v->nxt; // double linked list, delete v
    u->nxt = nxt, v->nxt = NULL, v->pre = NULL;
    if (nxt) nxt->pre = u;
}
template <typename T> void BPlusTree<T>::pushup(Node<T> *u){
    if(!u) return;
    u->sz = 0;
    if (u->t == LEAF){
        for (int i = 0; i < u->cnt; ++i) u->sz += (*u->val)[i]->leaf_key->count;
    }else{
        for (int i = 0; i <= u->cnt; ++i) u->sz += u->son[i]->sz;
    }
}
template <typename T> void BPlusTree<T>::insert_internal_right_by_id(Node<T> *u, int id, Node<T> *s, SkipList<T> *val){ 
    // insert val[id] and son[id + 1]
    for (int i = u->cnt; i >= id + 1; --i) u->son[i + 1] = u->son[i];
    u->son[id + 1] = s;
    // , s->fa = u;
    u->val->insert_internal(val);
    ++u->cnt, pushup(u);
}
template <typename T> void BPlusTree<T>::insert_leaf_by_id(Node<T> *u, int id, Value<T> *val){ 
    // insert val[id]
    u->val->insert_leaf(val);
    ++u->cnt, pushup(u);
}
template <typename T> void BPlusTree<T>::insert_internal_left_by_id(Node<T> *u, int id, Node<T> *s, SkipList<T> *val){ 
    // insert val[id] and son[id]
    for (int i = u->cnt; i >= id; --i) u->son[i + 1] = u->son[i];
    u->son[id] = s;
    // , s->fa = u;
    u->val->insert_internal(val);
    ++u->cnt, pushup(u);
}
template <typename T> Value<T>* BPlusTree<T>::delete_leaf_by_id(Node<T> *u, int id){ 
    // delete val[id]
    Value<T> *deleted_val = (*u->val)[id]->leaf_key;
    u->val->erase_leaf(deleted_val);
    u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> SkipList<T>* BPlusTree<T>::delete_internal_right_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id + 1]
    SkipList<T> *deleted_val = ((*u->val)[id]) ? (*u->val)[id]->internal_key : NULL;
    for (int i = id + 1; i < u->cnt; ++i) u->son[i] = u->son[i + 1];
    u->son[u->cnt] = NULL;
    // u->val->erase_internal(deleted_val);
    pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, id + 1);
    pair<SkipList<T>*, SkipList<T>* > q = splitlist(p.second, 2);
    u->val = mergelist(p.first, q.second);
    delete q.first, q.first = nullptr;
    delete q.second, q.second = nullptr;
    u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> SkipList<T>* BPlusTree<T>::delete_internal_left_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id]
    SkipList<T> *deleted_val = (*u->val)[id]->internal_key;
    for (int i = id + 1; i <= u->cnt; ++i) u->son[i - 1] = u->son[i];
    u->son[u->cnt] = NULL;
    // u->val->erase_internal(deleted_val);
    pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, id + 1);
    pair<SkipList<T>*, SkipList<T>* > q = splitlist(p.second, 2);
    u->val = mergelist(p.first, q.second);
    delete q.first, q.first = nullptr;
    delete q.second, q.second = nullptr;
    u->cnt--, pushup(u);
    return deleted_val;
}
template <typename T> void BPlusTree<T>::split(Node<T> *u, Node<T> *fa){
    int mid = (u->t == LEAF) ? M / 2 : (M - 1) / 2;
    // Node<T> *fa = u->fa;
    if (!fa) root = fa = new Node<T>(INTERNAL, NULL), fa->son[0] = u; //, u->fa = fa;
    Node<T> *v = new Node<T>(u->t, fa);
    int id = get_id(u, fa);
    SkipList<T> *value = NULL;
    if (u->t == LEAF){
        pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, mid + 1);
        u->val = p.first;
        delete v->val, v->val = p.second;
        u->cnt = mid, v->cnt = M - mid;
        linkin(u, v);
        value = v->val;
    }else{
        value = (*u->val)[mid]->internal_key;
        for (int i = mid + 1; i <= u->cnt; ++i){
            v->son[i - mid - 1] = u->son[i];
            // u->son[i]->fa = v, 
            u->son[i] = NULL;
        }
        pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, mid + 1);
        u->val = p.first;
        pair<SkipList<T>*, SkipList<T>* > q = splitlist(p.second, 2);
        delete q.first;
        delete v->val, v->val = q.second;
        u->cnt = mid, v->cnt = M - mid - 1;
    }

    insert_internal_right_by_id(fa, id, v, value);
    pushup(u), pushup(v);
}
template <typename T> void BPlusTree<T>::insert(Node<T> *u, Node<T> *fa, T val){
    if (!root){
        root = new Node<T>(LEAF, NULL);
        insert_leaf_by_id(root, 0, new Value<T>(val, 1));
        pushup(root);
        return;
    }
    int i = traverse(u, val);
    if (u->t == INTERNAL) insert(u->son[i], u, val);
    else{
        if (i < u->cnt && val == (*u->val)[i]->leaf_key->value){
            ++(*u->val)[i]->leaf_key->count, pushup(u);
            return;
        }
        insert_leaf_by_id(u, i, new Value<T>(val, 1));
    }
    if (u->cnt >= M) split(u, fa);
    pushup(u);
}
template <typename T> void BPlusTree<T>::merge(Node<T> *u, Node<T> *v, Node<T> *fa){
    // Node<T> *fa = u->fa;
    int id = get_id(u, fa);
    if (u->t == LEAF){
        u->val = mergelist(u->val, v->val);
        u->cnt += v->cnt, v->cnt = 0;
        linkout(u, v);
    }else{
        insert_internal_right_by_id(u, u->cnt, v->son[0], (*fa->val)[id]->internal_key);
        for (int i = 0; i < v->cnt; ++i){
            u->son[++u->cnt] = v->son[i + 1];
            // v->son[i + 1]->fa = u, 
            v->son[i + 1] = NULL;
        }
        u->val = mergelist(u->val, v->val);
        v->cnt = 0;
    }
    delete_internal_right_by_id(fa, id); // what if this sentence is put in front of if (u->t == LEAF) sentence?
    delete v, v = nullptr;
    pushup(u);
}
template <typename T> void BPlusTree<T>::fix(Node<T> *u, Node<T> *fa){
    // Node<T> *fa = u->fa;
    int id = get_id(u, fa);
    if (!fa) return;

    if (id > 0 && fa->son[id - 1]->cnt > m){ // borrow pre
        Node<T> *v = fa->son[id - 1];
        if(u->t == LEAF){
            Value<T> *pre = (*v->val)[v->cnt - 1]->leaf_key;
            insert_leaf_by_id(u, 0, pre);
            delete_leaf_by_id(v, v->cnt - 1);
        }else{
            Node<T> *s = v->son[v->cnt];
            SkipList<T> *pre = (*fa->val)[id - 1]->internal_key;
            (*fa->val)[id - 1]->internal_key = (*v->val)[v->cnt - 1]->internal_key; // change parent
            insert_internal_left_by_id(u, 0, s, pre);
            delete_internal_right_by_id(v, v->cnt - 1);
        }
        pushup(u), pushup(v);
    }else if (id < fa->cnt && fa->son[id + 1]->cnt > m){ // borrow nxt
        Node<T> *v = fa->son[id + 1];
        if(u->t == LEAF){
            Value<T> *nxt = (*v->val)[0]->leaf_key;
            delete_leaf_by_id(v, 0);               
            insert_leaf_by_id(u, u->cnt, nxt); 
        }else{
            Node<T> *s = v->son[0];
            SkipList<T> *nxt = (*fa->val)[id]->internal_key;
            (*fa->val)[id]->internal_key = (*v->val)[0]->internal_key; // change parent
            delete_internal_left_by_id(v, 0);               
            insert_internal_right_by_id(u, u->cnt, s, nxt); 
        }
        pushup(u), pushup(v);
    }else{
        if (id > 0) merge(fa->son[id - 1], u, fa);
        else merge(u, fa->son[id + 1], fa);
    }
}
template <typename T> void BPlusTree<T>::erase(Node<T> *u, Node<T> *fa, T val){
    int i = traverse(u, val);
    if (u->t == INTERNAL) erase(u->son[i], u, val);
    else{
        if (i >= u->cnt || (*u->val)[i]->leaf_key->value != val) return; // not found
        if ((*u->val)[i]->leaf_key->count > 1){
            --(*u->val)[i]->leaf_key->count, pushup(u);
            return;
        }
        Value<T> *deleted_value = delete_leaf_by_id(u, i);
        delete deleted_value, deleted_value = nullptr;
    }
    if (u == root && !u->cnt){
        root = u->son[0];
        // if(root) root->fa = NULL, pushup(root);
        pushup(root);
        delete u, u = nullptr;
        return;
    }
    if (u->cnt < m) fix(u, fa);
    pushup(u);
}
template <typename T> int BPlusTree<T>::getrank(Node<T> *u, T val){
    int i = traverse(u, val);
    if (u->t == INTERNAL){
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += u->son[j]->sz;
        return rank + getrank(u->son[i], val);
    }else{
        int rank = 0;
        for (int j = 0; j < i; ++j) rank += (*u->val)[j]->leaf_key->count;
        return rank + 1;
    }
}
template <typename T> T BPlusTree<T>::getval(Node<T> *u, int rank){
    int i = 0;
    if (u->t == INTERNAL){
        for (; i <= u->cnt; ++i){
            if (rank <= u->son[i]->sz) break;
            else rank -= u->son[i]->sz;
        }
        return getval(u->son[i], rank);
    }else{
        for (; i < u->cnt; ++i){
            if (rank >= 1 && rank <= (*u->val)[i]->leaf_key->count) return (*u->val)[i]->leaf_key->value;
            else rank -= (*u->val)[i]->leaf_key->count;
        }
    }
}
template <typename T> int BPlusTree<T>::getpre(Node<T> *u, T val){
    int i = traverse(u, val);
    if (u->t == INTERNAL) return getpre(u->son[i], val);
    else{
        if (i == 0) u = u->pre, i = u->cnt;
        assert(u != NULL);
        return (*u->val)[i - 1]->leaf_key->value;
    }
}
template <typename T>int BPlusTree<T>::getnxt(Node<T> *u, T val){
    int i = Traverse(u, val);
    if (u->t == INTERNAL) return getnxt(u->son[i], val);
    else{
        if (i == u->cnt) u = u->nxt, i = 0;
        assert(u != NULL);
        return (*u->val)[i]->leaf_key->value;
    }
}
void solve(){
    scanf("%d", &n);
    BPlusTree<int> *S = new BPlusTree<int>();
    for (int i = 1; i <= n; ++i){
        int op, x;
        scanf("%d%d", &op, &x);
        o = i;
        if (op == 1){
            S->insert(S->root, NULL, x);
        }else if (op == 2){
            S->erase(S->root, NULL, x);
        }else if (op == 3){
            printf("%d\n", S->getrank(S->root, x));
        }else if (op == 4){
            printf("%d\n", S->getval(S->root, x));
        }else if (op == 5){
            printf("%d\n", S->getpre(S->root, x));
        }else if (op == 6){
            printf("%d\n", S->getnxt(S->root, x));
        }
    }
    delete S;
}
int main(){
    for(int i=1;i<=1;++i){
        clock_t start = clock();
        freopen("P3369_14.in", "r", stdin);
        freopen("P3369_14.ans", "w", stdout);
        solve();
        clock_t end = clock();
        cerr<<end-start<<endl;
    }
    //solve();
    return 0;
}

复杂度正确跳表实现

这个版本 B+ 树 son 改成跳表, 只有 insert, erase 可用, 并且复杂度正确

与普通 B+ 树对比如下:

	普通 B+ 树	跳表 B+ 树
\(M=3\)	136ms	774ms
\(M=10000\)	2361ms	178ms

至于为什么 \(M=10000\) 比 \(M=3\) 更快, 可能是因为没有新建节点, 减少了增删节点的用时, 但通过与普通 B+ 树对比, 可以看出复杂度都是正确的

事实上 getpre, getnxt 也可以很方便的写出, 只有 getrank, getval 需要维护 sz 信息, 而我们不能使用 pushup, 就只能维护跳表

太麻烦就不写了

但是我用复杂度不对的 \(4\) 个查询函数测过, insert, erase 的正确性是没问题的

同时没有内存泄露, 并且 luogu P3369: AC

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8 + 10;
const int MAXL = 20;
const double p = 0.5;
const int M = 10000, m = (M - 1) / 2;
int n, ccnt, o;
template <typename T> class Node;
enum type {INTERNAL, LEAF};
template <typename T> struct Value{
public:
    T value;
    int count;
    Value<T>(T value, int count) : value(value), count(count) {}
    Value<T>() {}
    ~Value<T>() {}
    bool operator<(const Value<T> &x) const{
        return value < x.value;
    }
};
/*--------------------- Value List---------------------- */
template <typename T> class SkipList;
template <typename T> class SLNode{
public:
    SLNode<T> **forward;
    int *next;
    Value<T> *leaf_key;
    SkipList<T> *internal_key;
    type t;
    int level;
    SLNode<T>() {}
    ~SLNode<T>() {
        delete [] forward;
        delete [] next;
    }
    SLNode<T>(Value<T> *leaf_key, SkipList<T> *internal_key, type t) : 
        leaf_key(leaf_key), internal_key(internal_key), t(t) {
        next = new int [MAXL + 1];
        forward = new SLNode<T> *[MAXL + 1]; 
        for (int i = 0; i <= MAXL; ++i)
            forward[i] = NULL, next[i] = 0;
        level = RandomLevel();
    }
    int RandomLevel(){
        int lv = 0;
        int maxn = 1023;
        while (lv < MAXL && rand() % maxn < (int)(p * maxn)) ++lv;
        return lv;
    }
    friend class SkipList<T>;
};
template <typename T> class SkipList {
public:
    int level;
    int length;
    type t;
    SLNode<T> *head;
    SkipList<T>(type t) :t(t) { head = new SLNode<T>(0, 0, t), level = 0, length = 0; }
    ~SkipList<T>() {
        SLNode<T> *p = head;
        while(p){
            SLNode<T> *q = p->forward[0];
            delete p, p = q;
        }   
    }
    SLNode<T>* operator [](int rank){ // from 0
        // speed up internal_key to O(1)
        if(rank == 0) return head->forward[0];
        ++rank;
        SLNode<T> *p = head;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->next[i] < rank)
                rank -= p->next[i], p = p->forward[i];
        }
        p = p->forward[0];
        return p;
    }
    int getrank_leaf(T key){
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->leaf_key->value < key)
                now += p->next[i], p = p->forward[i];
        }
        return now + 1;
    }
    int getrank_Leaf(T key){
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->leaf_key->value <= key)
                now += p->next[i], p = p->forward[i];
        }
        return now + 1;
    }
    int getrank_internal(T key){
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && (*p->forward[i]->internal_key)[0]->leaf_key->value <= key)
                now += p->next[i], p = p->forward[i];
        }
        return now + 1;
    }
    void insert_leaf(Value<T> *key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->leaf_key->value < key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++; // now += p->next[0]
        SLNode<T> *NewNode = new SLNode<T>(key, NULL, t);
        if (level < NewNode->level){
            NewNode->level = head->level = ++level;
            update[level] = head, pos[level] = 0;
        }
        for (int i = 0; i <= level; ++i){
            p = update[i];
            if (i <= NewNode->level){
                NewNode->forward[i] = p->forward[i];
                if (p->forward[i]) NewNode->next[i] = p->next[i] - (now - pos[i]) + 1;
                else NewNode->next[i] = 0;
                p->next[i] = now - pos[i];
                p->forward[i] = NewNode;
            }else{
                if (p->forward[i]) p->next[i]++;
                else p->next[i] = 0;
            }
        }
        length++;
    }

    void insert_internal(SkipList<T> *key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && (*p->forward[i]->internal_key)[0]->leaf_key->value < (*key)[0]->leaf_key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++; // now += p->next[0]
        SLNode<T> *NewNode = new SLNode<T>(NULL, key, t);
        if (level < NewNode->level){
            NewNode->level = head->level = ++level;
            update[level] = head, pos[level] = 0;
        }
        for (int i = 0; i <= level; ++i){
            p = update[i];
            if (i <= NewNode->level){
                NewNode->forward[i] = p->forward[i];
                if (p->forward[i]) NewNode->next[i] = p->next[i] - (now - pos[i]) + 1;
                else NewNode->next[i] = 0;
                p->next[i] = now - pos[i];
                p->forward[i] = NewNode;
            }else{
                if (p->forward[i]) p->next[i]++;
                else p->next[i] = 0;
            }
        }
        length++;
    }


    bool erase_leaf(Value<T> *key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->forward[i]->leaf_key->value < key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++;
        if (!p || p->leaf_key->value != key->value)
            return false;

        for (int i = 0; i <= level; ++i){
            if (update[i]->forward[i] != p){
                if (update[i]->forward[i]) update[i]->next[i]--;
                else update[i]->next[i] = 0;
            }else{
                update[i]->forward[i] = p->forward[i];
                update[i]->next[i] += p->next[i] - 1;
            }
        }
        delete p;
        while (level > 0 && head->forward[level] == NULL) level--;
        head->level = level;
        length--;
        return true;
    }

    bool erase_internal(SkipList<T> *key){
        SLNode<T> *update[MAXL + 1];
        int pos[MAXL + 1];
        SLNode<T> *p = head;
        int now = 0;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && (*p->forward[i]->internal_key)[0]->leaf_key->value < (*key)[0]->leaf_key->value)
                now += p->next[i], p = p->forward[i];
            update[i] = p, pos[i] = now;
        }
        p = p->forward[0], now++;
        if (!p || (*p->internal_key)[0]->leaf_key->value != (*key)[0]->leaf_key->value)
            return false;

        for (int i = 0; i <= level; ++i){
            if (update[i]->forward[i] != p){
                if (update[i]->forward[i]) update[i]->next[i]--;
                else update[i]->next[i] = 0;
            }else{
                update[i]->forward[i] = p->forward[i];
                update[i]->next[i] += p->next[i] - 1;
            }
        }
        delete p;
        while (level > 0 && head->forward[level] == NULL) level--;
        head->level = level;
        length--;
        return true;
    }
};
template <typename T> pair<SkipList<T>*, SkipList<T>*> splitlist(SkipList<T>* u, int rank){
    SkipList<T>* v = new SkipList<T>(u->t);
    SLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    SLNode<T> *p = u->head;
    int now = 0, level = u->level;
    for (int i = level; i >= 0; --i){
        while (p->forward[i] != NULL && now + p->next[i] < rank)
            now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    v->level = level, v->head->level = level;
    v->length = u->length - now + 1, u->length = now - 1;
    for (int i = 0; i <= level; ++i){
        p = update[i];
        v->head->forward[i] = p->forward[i];
        if (p->forward[i]) v->head->next[i] = p->next[i] - (now - pos[i]) + 1;
        else v->head->next[i] = 0;
        p->next[i] = 0;
        p->forward[i] = NULL;
    }
    return make_pair(u, v);
}
template <typename T> SkipList<T>* mergelist(SkipList<T>* u, SkipList<T>* v){
    SLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    SLNode<T> *p = u->head;
    int now = 0;
    for (int i = u->level; i >= 0; --i){
        while (p->forward[i] != NULL) now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    for (int i = 0; i <= v->level; ++i){
        if(i > u->level){
            u->head->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) u->head->next[i] = u->length + v->head->next[i];
            else u->head->next[i] = 0;
        }else{
            update[i]->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) update[i]->next[i] = (u->length - pos[i]) + v->head->next[i];
            else update[i]->next[i] = 0;
        }
        v->head->forward[i] = NULL;
    }
    u->level = max(u->level, v->level);
    u->head->level = u->level;
    u->length += v->length, v->length = 0;
    // delete v; // v will be deleted in B+ tree (when Node is deleted, Node->Value will also be deleted)
    return u;
}
/*--------------------- Node List---------------------- */

template <typename T> class NodeSkipList;
template <typename T> class NodeSLNode{
public:
    NodeSLNode<T> **forward;
    int *next;
    Node<T> *key;
    type t;
    int level;
    NodeSLNode<T>() {}
    ~NodeSLNode<T>() {
        delete [] forward;
        delete [] next;
    }
    NodeSLNode<T>(Node<T> *key) : key(key) {
        next = new int [MAXL + 1];
        forward = new NodeSLNode<T> *[MAXL + 1]; 
        for (int i = 0; i <= MAXL; ++i)
            forward[i] = NULL, next[i] = 0;
        level = RandomLevel();
    }
    int RandomLevel(){
        int lv = 0;
        int maxn = 1023;
        while (lv < MAXL && rand() % maxn < (int)(p * maxn)) ++lv;
        return lv;
    }
    friend class NodeSkipList<T>;
};
template <typename T> class NodeSkipList {
public:
    int level;
    int length;
    int size;
    type t;
    NodeSLNode<T> *head;
    NodeSkipList<T>() { head = new NodeSLNode<T>(0), size = 0, level = 0, length = 0; }
    ~NodeSkipList<T>() {
        NodeSLNode<T> *p = head;
        while(p){
            NodeSLNode<T> *q = p->forward[0];
            delete p, p = q;
        }   
    }
    NodeSLNode<T>* operator [](int rank){ // from 0
        // speed up internal_key to O(1)
        if(rank == 0) return head->forward[0];
        ++rank;
        NodeSLNode<T> *p = head;
        for (int i = level; i >= 0; --i){
            while (p->forward[i] != NULL && p->next[i] < rank)
                rank -= p->next[i], p = p->forward[i];
        }
        p = p->forward[0];
        return p;
    }
    void insert(Node<T> *key){
        NodeSLNode<T> *NewNode = new NodeSLNode<T>(key);
        if (level < NewNode->level)
            NewNode->level = head->level = ++level;        
        for (int i = 0; i <= level; ++i){
            head->next[i] = 1, head->forward[i] = NewNode;
            NewNode->next[i] = 0, NewNode->forward[i] = NULL;
        }
        length = 1;
    }
};
template <typename T> pair<NodeSkipList<T>*, NodeSkipList<T>*> SplitList(NodeSkipList<T>* u, int rank){
    NodeSkipList<T>* v = new NodeSkipList<T>();
    NodeSLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    NodeSLNode<T> *p = u->head;
    int now = 0, level = u->level;
    for (int i = level; i >= 0; --i){
        while (p->forward[i] != NULL && now + p->next[i] < rank)
            now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    v->level = level, v->head->level = level;
    v->length = u->length - now + 1, u->length = now - 1;
    for (int i = 0; i <= level; ++i){
        p = update[i];
        v->head->forward[i] = p->forward[i];
        if (p->forward[i]) v->head->next[i] = p->next[i] - (now - pos[i]) + 1;
        else v->head->next[i] = 0;
        p->next[i] = 0, p->forward[i] = NULL;
    }
    return make_pair(u, v);
}
template <typename T> NodeSkipList<T>* MergeList(NodeSkipList<T>* u, NodeSkipList<T>* v){
    NodeSLNode<T> *update[MAXL + 1];
    int pos[MAXL + 1];
    NodeSLNode<T> *p = u->head;
    int now = 0;
    for (int i = u->level; i >= 0; --i){
        while (p->forward[i] != NULL) now += p->next[i], p = p->forward[i];
        update[i] = p, pos[i] = now;
    }
    p = p->forward[0], now++; // now += p->next[0]
    for (int i = 0; i <= v->level; ++i){
        if(i > u->level){
            u->head->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) u->head->next[i] = u->length + v->head->next[i];
            else u->head->next[i] = 0;
        }else{
            update[i]->forward[i] = v->head->forward[i];
            if(v->head->forward[i]) update[i]->next[i] = (u->length - pos[i]) + v->head->next[i];
            else update[i]->next[i] = 0;
        }
        v->head->forward[i] = NULL;
    }
    u->level = max(u->level, v->level);
    u->head->level = u->level;
    u->length += v->length, v->length = 0;
    // delete v; // v will be deleted in B+ tree (when Node is deleted, Node->Value will also be deleted)
    return u;
}
/*--------------------- BPlusTree ---------------------- */
template <typename T> class Node{
public:
    Node<T> *fa, *nxt, *pre;
    NodeSkipList<T> *son;
    SkipList<T> *val;
    int sz;
    type t;
    Node<T>(type t, Node<T> *fa) : t(t), fa(fa){
        nxt = pre = NULL;
        val = new SkipList<T>(t);
        son = new NodeSkipList<T>();
    }
    Node<T>() {}
    ~Node<T>() {delete son, delete val; } // add this line will cause luogu P3369 RE
};
template <typename T> class BPlusTree{
private:
    int traverse(Node<T> *u, T val);
    int Traverse(Node<T> *u, T val);
    void insert_internal_right_by_id(Node<T> *u, int id, Node<T> *s, SkipList<T> *val);
    void insert_leaf_by_id(Node<T> *u, int id, Value<T> *val);
    void insert_internal_left_by_id(Node<T> *u, int id, Node<T> *s, SkipList<T> *val);
    SkipList<T>* delete_internal_right_by_id(Node<T> *u, int id);
    Value<T>* delete_leaf_by_id(Node<T> *u, int id);
    SkipList<T>* delete_internal_left_by_id(Node<T> *u, int id);
    void linkin(Node<T> *u, Node<T> *v);
    void linkout(Node<T> *u, Node<T> *v);
    void split(Node<T> *u, Node<T> *fa, int id);
    void merge(Node<T> *u, Node<T> *v, Node<T> *fa, int id);
    void fix(Node<T> *u, Node<T> *fa, int id);
    void clear(Node<T> *u){
        if(!u) return;
        NodeSLNode<T> *p = u->son->head->forward[0];
        while(p) 
            clear(p->key), p = p->forward[0];
        delete u, u = nullptr;
    }
    void destroy(Node<T> *u){
        while(u && u->t == INTERNAL) u = (*u->son)[0]->key;
        while(u){
            SLNode<T> *p = u->val->head->forward[0];
            while(p){
                delete p->leaf_key, p->leaf_key = nullptr;
                p = p->forward[0];
            }
            u = u->nxt;
        }
    }
public:
    Node<T> *root;
    void insert(Node<T> *u, Node<T> *fa, T val, int id);
    void erase(Node<T> *u, Node<T> *fa, T val, int id);
    int getrank(Node<T> *x, T val);
    T getval(Node<T> *x, int rank);
    int getpre(Node<T> *x, T val);
    int getnxt(Node<T> *x, T val);
    BPlusTree<T>() { root = NULL; }
    ~BPlusTree<T>() { destroy(root); clear(root); }
    void dfs(Node<T> *x) {
        assert(x!=NULL);
        cerr<<x->val<<"(type="<<(x->t==LEAF?"LEAF":"INTERNAL")<<",cnt="<<x->val->length;
        cerr<<")->[";
        SLNode<T> *p = x->val->head->forward[0];
        if(x->t == LEAF){
            while(p){
                if(p->leaf_key) cerr << p->leaf_key->value << " ";
                else cerr << "NULL ";
                p = p->forward[0];
            }
        }else{
            while(p){
                if((*p->internal_key)[0]) cerr << (*p->internal_key)[0]->leaf_key->value << " ";
                else cerr << "NULL ";
                p = p->forward[0];
            }
        }
        cerr<<"]\n";
        if(x->t==LEAF) return;
        NodeSLNode<T> *q = x->son->head->forward[0];
        while(q){
            dfs(q->key);
            q = q->forward[0];
        }
    }
};
template<typename T> int BPlusTree<T>::traverse(Node<T> *u, T val){
    int i = 0;
    if(u->t == LEAF) i = u->val->getrank_leaf(val) - 1;
    else i = u->val->getrank_internal(val) - 1;
    return i;
}
template<typename T> int BPlusTree<T>::Traverse(Node<T> *u, T val){
    int i = 0;
    if(u->t == LEAF) i = u->val->getrank_Leaf(val) - 1; // different
    else i = u->val->getrank_internal(val) - 1;
    return i;
}
template <typename T> void BPlusTree<T>::linkin(Node<T> *u, Node<T> *v){
    Node<T> *nxt = u->nxt; // double linked list, insert v
    v->nxt = u->nxt, v->pre = u, u->nxt = v;
    if(nxt) nxt->pre = v;
}
template <typename T> void BPlusTree<T>::linkout(Node<T> *u, Node<T> *v){
    Node<T> *nxt = v->nxt; // double linked list, delete v
    u->nxt = nxt, v->nxt = NULL, v->pre = NULL;
    if (nxt) nxt->pre = u;
}
template<typename T> void insert_son(Node<T> *u, Node<T> *s, int id){
    pair<NodeSkipList<T>*, NodeSkipList<T>* > p = SplitList(u->son, id + 1);
    NodeSkipList<T>* q = new NodeSkipList<T>();
    q->insert(s);
    u->son = MergeList(p.first, MergeList(q, p.second));
    delete p.second, p.second = nullptr;
    delete q, q = nullptr;
}
template<typename T> void delete_son(Node<T> *u, int id){
    pair<NodeSkipList<T>*, NodeSkipList<T>* > p = SplitList(u->son, id + 1);
    pair<NodeSkipList<T>*, NodeSkipList<T>* > q = SplitList(p.second, 2);
    u->son = MergeList(p.first, q.second);
    delete q.first, q.first = nullptr;
    delete q.second, q.second = nullptr;
}
template<typename T> void erase_val(Node<T> *u, int id){
    pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, id + 1);
    pair<SkipList<T>*, SkipList<T>* > q = splitlist(p.second, 2);
    u->val = mergelist(p.first, q.second);
    delete q.first, q.first = nullptr;
    delete q.second, q.second = nullptr;
}
template <typename T> void BPlusTree<T>::insert_internal_right_by_id(Node<T> *u, int id, Node<T> *s, SkipList<T> *val){ 
    // insert val[id] and son[id + 1]
    insert_son(u, s, id + 1);
    u->val->insert_internal(val);
}
template <typename T> void BPlusTree<T>::insert_leaf_by_id(Node<T> *u, int id, Value<T> *val){ 
    // insert val[id]
    u->val->insert_leaf(val);
}
template <typename T> void BPlusTree<T>::insert_internal_left_by_id(Node<T> *u, int id, Node<T> *s, SkipList<T> *val){ 
    // insert val[id] and son[id]
    insert_son(u, s, id);
    u->val->insert_internal(val);
}
template <typename T> Value<T>* BPlusTree<T>::delete_leaf_by_id(Node<T> *u, int id){ 
    // delete val[id]
    Value<T> *deleted_val = (*u->val)[id]->leaf_key;
    u->val->erase_leaf(deleted_val);
    return deleted_val;
}
template <typename T> SkipList<T>* BPlusTree<T>::delete_internal_right_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id + 1]
    SkipList<T> *deleted_val = ((*u->val)[id]) ? (*u->val)[id]->internal_key : NULL;
    delete_son(u, id + 1), erase_val(u, id);
    return deleted_val;
}
template <typename T> SkipList<T>* BPlusTree<T>::delete_internal_left_by_id(Node<T> *u, int id){ 
    // delete val[id] and son[id]
    SkipList<T> *deleted_val = ((*u->val)[id]) ? (*u->val)[id]->internal_key : NULL;
    delete_son(u, id), erase_val(u, id);
    return deleted_val;
}
template <typename T> void BPlusTree<T>::split(Node<T> *u, Node<T> *fa, int id){
    int mid = (u->t == LEAF) ? M / 2 : (M - 1) / 2;
    if (!fa){
        root = fa = new Node<T>(INTERNAL, NULL);
        fa->son->insert(u);
    }
    Node<T> *v = new Node<T>(u->t, fa);
    SkipList<T> *value = NULL;
    if (u->t == LEAF){
        pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, mid + 1);
        u->val = p.first;
        delete v->val, v->val = p.second;
        linkin(u, v);
        value = v->val;
    }else{
        value = (*u->val)[mid]->internal_key;
        pair<NodeSkipList<T>*, NodeSkipList<T>* > f = SplitList(u->son, mid + 2);
        u->son = f.first;
        delete v->son, v->son = f.second;
        pair<SkipList<T>*, SkipList<T>* > p = splitlist(u->val, mid + 1);
        u->val = p.first;
        pair<SkipList<T>*, SkipList<T>* > q = splitlist(p.second, 2);
        delete q.first, q.first = nullptr;
        delete v->val, v->val = q.second;
    }
    insert_internal_right_by_id(fa, id, v, value);
}
template <typename T> void BPlusTree<T>::insert(Node<T> *u, Node<T> *fa, T val, int id){
    if (!root){
        root = new Node<T>(LEAF, NULL);
        insert_leaf_by_id(root, 0, new Value<T>(val, 1));
        return;
    }
    int i = traverse(u, val);
    if (u->t == INTERNAL) insert((*u->son)[i]->key, u, val, i);
    else{
        if (i < u->val->length && val == (*u->val)[i]->leaf_key->value){
            ++(*u->val)[i]->leaf_key->count;
            return;
        }
        insert_leaf_by_id(u, i, new Value<T>(val, 1));
    }
    if (u->val->length >= M) split(u, fa, id);
}
template <typename T> void BPlusTree<T>::merge(Node<T> *u, Node<T> *v, Node<T> *fa, int id){
    if (u->t == LEAF){
        u->val = mergelist(u->val, v->val);
        linkout(u, v);
    }else{
        insert_internal_right_by_id(u, u->val->length, (*v->son)[0]->key, (*fa->val)[id]->internal_key);
        pair<NodeSkipList<T> *, NodeSkipList<T> *> p = SplitList(v->son, 2);
        u->son = MergeList(u->son, p.second);
        delete p.second, p.second = nullptr;
        u->val = mergelist(u->val, v->val);   
    }
    delete_internal_right_by_id(fa, id); // what if this sentence is put in front of if (u->t == LEAF) sentence?
    delete v, v = nullptr;
}
template <typename T> void BPlusTree<T>::fix(Node<T> *u, Node<T> *fa, int id){
    if (!fa) return;
    if (id > 0 && (*fa->son)[id - 1]->key->val->length > m){ // borrow pre 
        Node<T> *v = (*fa->son)[id - 1]->key;
        if(u->t == LEAF){
            Value<T> *pre = (*v->val)[v->val->length - 1]->leaf_key;
            insert_leaf_by_id(u, 0, pre);
            delete_leaf_by_id(v, v->val->length - 1);
        }else{
            Node<T> *s = (*v->son)[v->val->length]->key;
            SkipList<T> *pre = (*fa->val)[id - 1]->internal_key;
            (*fa->val)[id - 1]->internal_key = (*v->val)[v->val->length - 1]->internal_key; // change parent
            insert_internal_left_by_id(u, 0, s, pre);
            delete_internal_right_by_id(v, v->val->length - 1);
        }
    }else if (id < fa->val->length && (*fa->son)[id + 1]->key->val->length > m){ // borrow nxt
        Node<T> *v = (*fa->son)[id + 1]->key;
        if(u->t == LEAF){
            Value<T> *nxt = (*v->val)[0]->leaf_key;
            delete_leaf_by_id(v, 0);               
            insert_leaf_by_id(u, u->val->length, nxt); 
        }else{
            Node<T> *s = (*v->son)[0]->key;
            SkipList<T> *nxt = (*fa->val)[id]->internal_key;
            (*fa->val)[id]->internal_key = (*v->val)[0]->internal_key; // change parent
            delete_internal_left_by_id(v, 0);               
            insert_internal_right_by_id(u, u->val->length, s, nxt); 
        }
    }else{
        if (id > 0) merge((*fa->son)[id - 1]->key, u, fa, id - 1);
        else merge(u, (*fa->son)[id + 1]->key, fa, id);
    }   
}
template <typename T> void BPlusTree<T>::erase(Node<T> *u, Node<T> *fa, T val, int id){
    int i = traverse(u, val);
    if (u->t == INTERNAL) erase((*u->son)[i]->key, u, val, i);
    else{
        if (i >= u->val->length || (*u->val)[i]->leaf_key->value != val) return; // not found
        if ((*u->val)[i]->leaf_key->count > 1){
            --(*u->val)[i]->leaf_key->count;
            return;
        }
        Value<T> *deleted_value = delete_leaf_by_id(u, i);
        delete deleted_value, deleted_value = nullptr;
    }
    if (u == root && !u->val->length){
        root = (*u->son)[0] ? (*u->son)[0]->key : NULL;
        delete u, u = nullptr;
        return;
    }
    if (u->val->length < m) fix(u, fa, id);
}
void solve(){
    scanf("%d", &n);
    BPlusTree<int> *S = new BPlusTree<int>();
    for (int i = 1; i <= n; ++i){
        int op, x;
        scanf("%d%d", &op, &x);
        o = i;
        if (op == 1){
            S->insert(S->root, NULL, x, 0);
        }else if (op == 2){
            S->erase(S->root, NULL, x, 0);
        }
    }
    delete S;
}
int main(){
    for(int i=1;i<=1;++i){
        clock_t start = clock();
        freopen("P3369_10.in", "r", stdin);
        freopen("P3369_10.ans", "w", stdout);
        solve();
        clock_t end = clock();
        cerr<<end-start<<endl;
    }
    return 0;
}