P1486 [NOI2004] 郁闷的出纳员题解

Infter · 2023-11-15 20:22:27 · 个人记录

跳表大法好（大乐）。

Des

要求编写数据结构具有以下操作：
插入元素 k。
将所有数据增加 k。
将所有数据减少 k。
查询第 k 大的值。
如果有元素在某个环节小于了 min，则直接退出数据结构。
特殊的，如果有元素加进来就不满足条件就不要加进来。
最后统计踢出去了多少个元素。

Sol

首先，我们把目光放到“将所有数据增加 k”上。

既然是所有元素一起加，我们就维护一个变量 c 代表整体增加了多少，减少同理。

但是就会有个问题：它在不断的新增元素怎么办？

实际上可以把加进来的 k 减去 c，这样就可以统一进行操作了。

现在，我们的问题转化为了维护三种操作:

插入元素。
删除元素。
查询第 k 大。

很多人都会想到平衡树，但是实际上有其他方法，就是跳表！

跳跃表（ skip list ）又称跳表，跳跃表在原有的有序链表上增加了多级索引，其中每一级索引都是一个有序链表。跳跃表通过索引实现快速查询。——《信息学奥林匹克辞典》 P245

你可以将其理解为多层的链表，每个点采用随机的方式，每次有 \frac12 的概率向上拓展一层，每一次进行查询，修改，都从最上层开始，走到头了就往下一层走。

具体的介绍见 \text{OI wiki}。

总而言之，跳表就是一种支持：

插入
删除
查询第 k 大
查询元素值对应的下标

的数据结构，且所有的操作都是期望 \Theta(\log n) 的。

Cod

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

const int MAXN = 3e5 + 5;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int MAXP = 16;
const double P = 0.36;

struct Node {
    Node* forward[MAXP];
    int dis[MAXP];
    int lay;
    long long body;
};
typedef Node* Nodeptr;
Nodeptr head, updata[MAXP];
int updata2[MAXP];
int mxlvl;
int n, lenth;

long long m, c;

void init() {
    head = new Node;
    mxlvl = 0;
    head->body = -INF;
    head->lay = 0;
    for (int i = 0; i < 16; i++) {
        head->forward[i] = nullptr;
        head->dis[i] = 0;
    }
}

int get_level() {
    int lay = 0;
    while (1.0 * rand() / RAND_MAX <= P and lay < MAXP - 1)
        lay++;
    return lay;
}

pair<Nodeptr, int> find(int x) {
    Nodeptr p = head;
    int y = 0;
    for (int i = mxlvl; i >= 0; i--) {
        while (p->forward[i] and p->forward[i]->body < x) {
            y += p->dis[i];
            p = p->forward[i];
        }
        updata[i] = p;
        updata2[i] = y;
    }
    return make_pair(p, y);
}

void insert(int x) {
    if (x < m)
        return;
    x -= c;
    lenth++;
    Nodeptr s = new Node;
    s->body = x;
    s->lay = get_level();
    mxlvl = max(mxlvl, s->lay);
    int tmp = find(x).second + 1;
    for (int i = mxlvl; i >= 0; i--) {
        if (i > s->lay) {
            updata[i]->dis[i]++;
        } else {
            Nodeptr p = updata[i];
            int p2 = updata2[i];
            if (p->forward[i] == 0) {
                s->forward[i] = nullptr;
                s->dis[i] = 0;
            } else {
                s->forward[i] = p->forward[i];
                s->dis[i] = p2 + p->dis[i] - tmp + 1;
            }
            p->forward[i] = s;
            p->dis[i] = tmp - p2;
        }
    }
}

int res = 0;

void erase(Nodeptr s) {
    res++;
    lenth--;
    find(s->body);
    for (int i = mxlvl; i >= 0; i--) {
        Nodeptr p = updata[i];
        Nodeptr q = s->forward[i];
        if (i > s->lay) {
            p->dis[i]--;
            continue;
        }
        p->forward[i] = q;
        if (!q)
            p->dis[i] = 0;
        else
            p->dis[i] = p->dis[i] + s->dis[i] - 1;
    }
    delete s;
    while (!head->forward[mxlvl])
        mxlvl--;
}

void inc(int k) {
    c += k;
}

void dec(int k) {
    c -= k;
    int t;
    while (1) {
        if (head->forward[0] == nullptr)
            return;
        t = head->forward[0]->body;
        if (t + c < m)
            erase(head->forward[0]);
        else
            return;
    }
}

long long search(int k) {
    if (k > lenth)
        return -1;
    k = lenth - k + 1;
    Nodeptr p = head;
    long long x = 0;
    for (int i = mxlvl; i >= 0; i--) {
        while (p->forward[i] and x + p->dis[i] <= k) {
            x += p->dis[i];
            p = p->forward[i];
        }
    }
    return p->body + c;
}

int main() {
    srand(time(NULL));

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    init();
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        // cerr << i << endl;
        string x;
        int k;
        cin >> x >> k;
        if (x == "I")
            insert(k);
        else if (x == "A")
            inc(k);
        else if (x == "S")
            dec(k);
        else
            cout << search(k) << endl;
    }

    cout << res << endl;

    return 0;
}

P1486 [NOI2004] 郁闷的出纳员 题解

Des

Sol

Cod

P1486 [NOI2004] 郁闷的出纳员题解