struct Node {
    int val;
    Node() {}
    Node(int V, int level) {
        val = V;
        node_level = level;
        forward = new Node*[level+1];
        memset(forward, 0, sizeof(Node*)*(level+1));
    }
    ~Node() {
        delete []forward;
    }

    Node **forward;
    int node_level;
};

class Skiplist {
public:
    Skiplist(int max_level = 18);
    ~Skiplist();
    
    bool search(int target);
    
    void add(int num);
    
    bool erase(int num);

    void display_list();

    int get_random_level();

private:
    int _max_level;

    int _skip_list_level;

    Node *_header;

    int _element_count;
};

Skiplist::Skiplist(int max_level) {
    _max_level = max_level;
    _header = new Node(-1, _max_level);
    _skip_list_level = 0;
    _element_count = 0;
}

Skiplist::~Skiplist() {
    delete _header;
}

bool Skiplist::search(int num) {
    Node *cur = _header;

    for ( int i=_skip_list_level;i>-1;--i )
        while ( cur->forward[i] && cur->forward[i]->val<num )
            cur = cur->forward[i];

    cur = cur->forward[0];
    if ( cur )
        return cur->val==num;
    return false;
}

void Skiplist::add(int num) {
    Node *cur = _header;
    Node *update[_max_level+1];
    memset(update, 0, sizeof(Node*)*(_max_level+1));

    for ( int i=_skip_list_level;i>=0;--i ) {
        // cout << "i = " << i << endl;
        while ( cur->forward[i]!=nullptr && cur->forward[i]->val<num )
            cur = cur->forward[i];
        update[i] = cur;
    }

    // for ( int i=0;i<=_skip_list_level;++i )
    //     cout << "update[" << i << "] = " << update[i]->val << endl;

    int rand_level = get_random_level();
    // cout << endl << "rand_level = " << rand_level ;
    if ( rand_level > _skip_list_level ) {
        for ( int i=_skip_list_level+1;i<=rand_level;++i )
            update[i] = _header;
        _skip_list_level = rand_level;
    }

    Node *new_Node = new Node(num, rand_level);
    for ( int i=0;i<=rand_level;++i ) {
        new_Node->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = new_Node;
    }

    _element_count++;
    return;
}

bool Skiplist::erase(int num) {
    Node *cur = _header;
    Node *update[_max_level+1];
    memset(update, 0, sizeof(Node*)*(_max_level+1));

    for ( int i=_skip_list_level;i>-1;--i ) {
        while ( cur->forward[i] && cur->forward[i]->val<num )
            cur = cur->forward[i];
        update[i] = cur;
    }
    cur = cur->forward[0];
    if ( cur && cur->val==num ) {
        for ( int i=0;i<_skip_list_level;++i ) {
            if ( update[i]->forward[i] !=cur ) {
                break;
            }    
            update[i]->forward[i] = cur->forward[i];
        }
        delete cur;
        _element_count--;
        while ( _skip_list_level>0 && _header->forward[_skip_list_level]==0 )
            _skip_list_level--;
        return true;
    }
    return false;
}

void Skiplist::display_list() {
    cout << "\n-------Skip List-------\n";
    for ( int i=_skip_list_level;i>=0;--i ) {
        Node *cur = _header->forward[i];
        cout << "Level " << i << ": header -> ";
        while ( cur!=nullptr ) {
            cout << cur->val << " -> ";
            cur = cur->forward[i];
        }
        cout << "NULL\n";
    }
}

int Skiplist::get_random_level() {
    int k = 1;
    while ( rand()%2 ) 
        k++;
    return (k<_max_level) ? k : _max_level;
}

bool Skiplist::erase(int num) {
    Node *cur = _header;
    Node *update[_max_level+1];
    memset(update, 0, sizeof(Node*)*(_max_level+1));

    for ( int i=_skip_list_level;i>-1;--i ) {
        while ( cur->forward[i] && cur->forward[i]->val<num )
            cur = cur->forward[i];
        update[i] = cur;
    }
    cur = cur->forward[0];
    if ( cur && cur->val==num ) {
        for ( int i=0;i<_skip_list_level;++i ) {
            if ( update[i]->forward[i] !=cur ) {
                break;
            }    
            update[i]->forward[i] = cur->forward[i];
        }
        // 问题就在此处，如果不delete，就能够AC
        // 但是如果delete，就会出现 heap-use-after-free 错误
        // 然而我在本地运行是可以delete的
        delete cur; 
        _element_count--;
        while ( _skip_list_level>0 && _header->forward[_skip_list_level]==0 )
            _skip_list_level--;
        return true;
    }
    return false;
}