CodeForces 1354D Multiset

十一月 05, 2020 2826

题意简述

给定一个可重集合，要求支持以下操作：

  • 插入一个数
  • 删除第 k 小的数

做完操作之后，输出任意一个属于该集合的数。

操作数、值域 \leq 10^6 ，空间限制 28MB。

解题思路

看见题目：我不会平衡树！我会权值线段树！

看见空间限制：我会权值树状数组！

看见值域：我。。。我不会了

但其实这题数据水的一批，直接在权值树状数组上 \mathcal{O}(n\log^2n) 二分就好了，居然还跑的飞快，最慢的点只跑了不到 500ms！

有兴趣的同学可以去学一下树状数组上二分，是一个 log 的但是我没调出来就索性水过了

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 1e6 + 10;

int n, q;

struct BIT {
    int ss[(1 << 21) + 10];
    
    #define lb(x) ((x) & (-(x)))
    void insert(int s, int x) {
        while (s <= n) ss[s] += x, s += lb(s);
    }
    int query(int rank) {
        int root = 0;
        for (int i = 20; i >= 0; --i) {
            int delta = (1 << i);
            // printf("root = %d, delta = %d\n", root, delta);
            if (root + delta <= n && ss[root + delta] <= rank) {
                root += delta; rank -= ss[root];
            } 
        } return root + 1;
    }
    int querysum(int x) {
        int ret = 0; while (x >= 1) {
            ret += ss[x]; x -= lb(x);
        } return ret;
    }
    int query_v2(int rank) {
        int l = 1, r = n, ans = n;
        while (l <= r) {
            // printf("now: l = %d, r = %d\n", l, r);
            int mid = (l + r) >> 1;
            if (querysum(mid) >= rank) r = mid - 1, ans = mid;
            else l = mid + 1;
        } return ans;
    }
} bit;

int main() {
    n = read(); q = read(); int siz = n;
    for (int i = 1; i <= n; ++i) bit.insert(read(), 1);
    for (int i = 1; i <= q; ++i) {
        int x = read();
        if (x > 0) { bit.insert(x, 1); ++siz; }
        else {
            bit.insert(bit.query_v2(-x), -1); --siz;
        }
        // printf("content: ");
        // for (int i = 1; i <= n; ++i) 
        //     printf("%d%c", bit.ss[i], " \n"[i == n]);
    } 
    if (siz == 0) puts("0");
    else printf("%d\n", bit.query_v2(1));
    return 0;
}