pain 2

skiplist_base.cpp

#include<bits/stdc++.h>
using namespace std;

struct Lehmer64
{
    using state_t=__uint128_t;
    using result_type=uint64_t;
    state_t state;
    uint64_t sm64(uint64_t x,uint64_t n)
    {
        x+=n*0x9e3779b97f4a7c15ull;
        x=(x^x>>30)*0xbf58476d1ce4e5b9ull;
        x=(x^x>>27)*0x94d049bb133111ebull;
        return x^x>>31;
    }
    const static state_t mult=0xda942042e4dd58b5;
    const static uint64_t def=-1;
    Lehmer64():state(state_t(sm64(def,1))<<64|sm64(def,2)){}
    Lehmer64(uint64_t seed):state(state_t(sm64(seed,1))<<64|sm64(seed,2)){}
    Lehmer64(const Lehmer64& a):state(a.state){}
    union lz{uint32_t st[4];state_t stt;};
    template<class Sseq>
    Lehmer64(Sseq& q){lz k;q.generate(k.st,k.st+4);state=k.stt;}
    void seed(){state=state_t(sm64(def,1))<<64|sm64(def,2);}
    void seed(uint64_t seed){state=state_t(sm64(seed,1))<<64|sm64(seed,2);}
    template<class Sseq>
    void seed(Sseq& q){lz k;q.generate(k.st,k.st+4);state=k.stt;}
    uint64_t operator()(){state*=mult;return state>>64;}
    template<class T>
    T pow(T a,uint64_t b){T z=1;do{if(b&1)z*=a;a*=a;}while(b/=2);return z;}
    void discard(uint64_t d){state*=pow(mult,d);}
    bool operator==(const Lehmer64& o){return state==o.state;}
    bool operator!=(const Lehmer64& o){return state!=o.state;}
    constexpr static uint64_t min(){return 0ull;}
    constexpr static uint64_t max(){return -1ull;}
};

template<class os>
os& operator<<(os& ost,const Lehmer64& L){ost<<uint64_t(L.state>>64)<<" "<<uint64_t(L.state);return ost;}
template<class is>
is& operator>>(is& ist,Lehmer64& L){uint64_t a,b;ist>>a>>b;L.state=a;L.state<<=64;L.state|=b;return ist;}

struct SkipList
{
    template<class T>
    struct Span
    {
        int size;T* data;
        T& operator[](int k)
        {
            //cout<<"size: "<<size<<", k: "<<k<<endl;
            if(k<0||k>=size)
            {
                throw out_of_range("span out of range");
            }
            return*(data+k);
        }
    };
    template<class T,int maxn=64>
    struct DataPool
    {
        vector<T>data;
        vector<Span<T>>degen[maxn+1];
        Span<T>alloc(int sz,T v=T{})
        {
            if(sz<=0||sz>maxn)throw out_of_range("alloc out of range");
            if(size(degen[sz])>0)
            {
                auto tmp=degen[sz].back();
                degen[sz].pop_back();
                fill(&tmp[0],&tmp[sz],v);
                return tmp;
            }
            int idx=size(data);
            data.resize(idx+sz,v);
            Span<T> S;
            S.data=&data[idx];
            S.size=sz;
            return S;
        }
        void dealloc(Span<T>S)
        {
            degen[S.size].push_back(S);
        }
    };
    struct NodePack
    {
        int H;
        Span<int>data;
        Span<int>lazy;
        Span<int>next_dist,prev_dist;
        Span<NodePack*>next;
        Span<NodePack*>prev;
    };

    DataPool<int>pool_int;
    DataPool<NodePack*>pool_link;
    vector<NodePack>nodes;

    void alloc(NodePack&N,int h)
    {
        N.H=h;
        N.data=pool_int.alloc(h);
        N.lazy=pool_int.alloc(h);
        N.next_dist=pool_int.alloc(h);
        N.prev_dist=pool_int.alloc(h);
        N.next=pool_link.alloc(h);
        N.prev=pool_link.alloc(h);
    }
    void dealloc(NodePack&N)
    {
        pool_int.dealloc(N.data);
        pool_int.dealloc(N.lazy);
        pool_int.dealloc(N.next_dist);
        pool_int.dealloc(N.prev_dist);
        pool_link.dealloc(N.next);
        pool_link.dealloc(N.prev);
    }

    void connect(NodePack&from,NodePack&to,int h,int dist)
    {
        from.next[h]=&to;
        to.prev[h]=&from;
        from.next_dist[h]=dist;
        to.prev_dist[h]=dist;
    }

    void insert_between(NodePack&before,NodePack&mid,NodePack&after,int h,int d1,int d2)
    {
        connect(before,mid,h,d1);
        connect(mid,after,h,d2);
    }

    SkipList()
    {
        lmr.seed(727);
        alloc(nodes.emplace_back(),64);
        alloc(nodes.emplace_back(),64);
        for(int i=0;i<64;i++)connect(nodes[0],nodes[1],i,1);
        nodes[0].data[0]=-999999;
        nodes[1].data[0]=-999999;
    }

    Lehmer64 lmr;

    int rnd_height()
    {
        return __builtin_ctzll(lmr())+1;
    }

    void insert(int k,int val)
    {
        int h=rnd_height();
        int pos_cur=-1;
        NodePack* to_con[64];
        to_con[63]=&nodes[0];
        if(k>pos_cur+nodes[0].next_dist[63])throw out_of_range("insert out of range");
        int pos_con[64];
        int pos_nxt[64];
        int cur_h=63;
        while(cur_h>=0)
        {
            while(pos_cur+to_con[cur_h]->next_dist[cur_h]<k)
            {
                pos_cur+=to_con[cur_h]->next_dist[cur_h];
                to_con[cur_h]=to_con[cur_h]->next[cur_h];
            }
            pos_con[cur_h]=pos_cur;
            if(cur_h>0)
            {
                to_con[cur_h-1]=to_con[cur_h];
            }
            cur_h--;
        }
        NodePack*to_next[64];
        for(int i=0;i<64;i++)
        {
            to_next[i]=to_con[i]->next[i];
            pos_nxt[i]=pos_con[i]+to_con[i]->next_dist[i];
        }
        
        alloc(nodes.emplace_back(),h);
        for(int i=0;i<h;i++)
        {
            insert_between(*to_con[i],nodes.back(),*to_next[i],i,k-pos_con[i],pos_nxt[i]-k+1);
        }
        for(int i=h;i<64;i++)
        {
            to_con[i]->next_dist[i]++;
            to_con[i]->prev_dist[i]++;
        }
        nodes.back().data[0]=val;
    }

    NodePack* node_at(int k)
    {
        int pos_cur=-1;
        NodePack* to_con[64];
        to_con[63]=&nodes[0];
        if(k>=pos_cur+nodes[0].next_dist[63])throw out_of_range("node_at out of range");
        int cur_h=63;
        while(cur_h>=0)
        {
            while(pos_cur+to_con[cur_h]->next_dist[cur_h]<=k)
            {
                pos_cur+=to_con[cur_h]->next_dist[cur_h];
                to_con[cur_h]=to_con[cur_h]->next[cur_h];
            }
            if(cur_h>0)
            {
                to_con[cur_h-1]=to_con[cur_h];
            }
            cur_h--;
        }
        return to_con[0];
    }

    int at(int k){return node_at(k)->data[0];}

    void erase(int k)
    {
        auto a=node_at(k);
        int h=a->H;
        for(int i=0;i<h;i++)
        {
            connect(*(a->prev[i]),*(a->next[i]),i,a->prev_dist[i]+a->next_dist[i]-1);
        }
        NodePack*cur=a->prev[h-1];
        for(int i=h;i<64;i++)
        {
            while(cur->H<(i+1)&&cur->prev[i-1]!=nullptr)cur=cur->prev[i-1];
            cur->next_dist[i]--;
            cur->next[i]->prev_dist[i]--;
        }
        dealloc(*a);
    }

    void debug()
    {
        NodePack*cur=&nodes[0];
        while(1)
        {
            cout<<"height: "<<cur->H<<endl;
            for(int i=0;i<cur->H;i++)
            {
                cout<<cur->data[i]<<" ";
            }
            cout<<endl;
            if(cur->next[0]!=nullptr)cur=cur->next[0];
            else break;
        }
    }
};

int main()
{
    SkipList SL;
    SL.insert(0,100);
    SL.insert(0,10);
    SL.insert(2,1000);
    cout<<SL.at(0)<<" "<<SL.at(1)<<" "<<SL.at(2)<<endl;
    SL.erase(1);
    SL.debug();
}