Algorithm

BIT在线求第k大数

在做小学期Day5C题（在线维护中位数）时，由于我没有做过，也没有想到正解（对顶堆），卡了很久，最后用一个奇怪的方法做出来了。发现这个奇怪的做法复杂度稍高，但是可以扩展。对顶堆只能维护中位数或固定k的第k大数，而奇怪做法可以（伪？）在线查找第k大数，k可变，代价是$O(\log^2 n)$的，$n$为数列长度。

步入正题。

开始为空的一个数列，有两种操作：

  1. 向数列中加入一个元素a
  2. 输入k，要求输出当前数列中第k大的数

首先加上一个限制：数列中的元素a是1到n之间的整数，且互不相同（这一条其实无所谓）。联想用BIT求解逆序对的方法，建立一棵权值BIT，再二分答案查找不超过当前答案的数的个数，目标是找到一个答案$ans$使得$sum(ans-1)<k$且$sum(ans)\geq k$，$sum$指BIT的求和操作，代表不超过$ans$的数的个数。每次获取个数的时间是$O(\log n)$的，共需要获取$O(\log n)$次，故复杂度为$O(\log^2 n)$。

现在去掉限制，允许$|A_i|\leq 10^{18}$，为了沿用上面的办法，需要将$A_i$映射到$[1,n]\cap\mathbb{N}$上，可以用unoerdered_map或gp_hash_table。但这种映射需要提前将所有$A_i$读进来，所以是（伪）在线，到底算不算在线我也不知道（？）。

给个这道题的AC代码。

AC代码

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
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
map<int, int> num, arcnum;
int a[maxn], b[maxn], n;
int bit[maxn];
void add(int id, int x)
{
    while(id < maxn)
    {
        bit[id] += x;
        id += (id & -id);
    }
}
int sum(int id)
{
    int ret = 0;
    while(id > 0)
    {
        ret += bit[id];
        id -= (id & -id);
    }
    return ret;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int cnt = 1;
    for (int i = 1; i <= n; i++) {
        num[b[i]] = cnt;
        arcnum[cnt] = b[i];
        cnt++;
    }
    for (int i = 1; i <= n; i++) {
        add(num[a[i]], 1);
        if((i & 1) == 0)
            continue;
        int l = 0, r = maxn, mid = 0;
        while(l + 1 < r) {
            mid = (l + r) >> 1;
            if(sum(mid) < (i + 1) / 2) {//修改(i+1)/2即可询问第k大的数
                l = mid;
            } else {
                r = mid;
            }
        }
        cout << arcnum[r] << '\n';
    }
    return 0;
}