题解 CF1354D 【Multiset】

· · 题解

楼上神犇用的都是 我听都没听过的东西。作为一个蒟蒻，只会用最简单的分块做。

时间复杂度插入 O(1) ，删除 O(\sqrt n) ，跑得飞快 勉强能过qwq。

不了解分块的童鞋可以先移步至 分块大法，当然这题并不需要那么多操作，只需了解基本概念即可。

题目数据 a_i 最大到1e6,所以我们可以十分愉快地把 1e6 分成 1000 块，每块管 1000 个数字。

记 num_i 为数字 i 出现的次数， fa_i 为第 i 块中数字的个数，容易看出数字 i 属于第 \frac{i-1}{1000} 块，所以在插入时只需 num_i ++， fa_\frac{i-1}{1000} ++即可；在删除时，分块的优势就体现出来了，一次可以判断一段，也就是 1000 个数字。

详见代码


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

#define maxn 1000005

int n, q;

int num[maxn], fa[1005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> q;
    int mx = 0; //记录出现的最大值，便于最后循环结束的判断，也可以不用。
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        num[x]++;             //桶中有的数+1
        fa[(x - 1) / 1000]++; //属于的块里有的数+1
        mx = max(mx, x);
    }
    while (q--) {
        int k;
        cin >> k;

        if (k > 0) {
            //插入操作 同读入
            num[k]++;
            fa[(k - 1) / 1000]++;
            mx = max(mx, k);
        }
        else {
            //删除操作
            k = -k; //别忘了k是负数

            //找第k个数属于第几块
            int index = 0;
            while (k > fa[index]) {
                k -= fa[index++];
            }

            // 此时已找到第k个数属于第index块，只需遍历这一块即可
            for (int i = index * 1000 + 1; i < index * 1000 + 1 + 1000; i++) {

                //找第k个数是多少
                if (k > num[i]) {
                    k -= num[i];
                }
                else {
                    //找到了第k个数
                    num[i]--; //桶-1
                    fa[(i - 1) / 1000]--; //属于的块里有的数-1
                    break;
                }
            }
        }
    }
    //找到数字就输出，没找到输出0。
    for (int i = 1; i <= mx; i++) {
        if (num[i]) {
            cout << i;
            return 0;
        }
    }
    cout << 0;
    return 0;
}