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代码

#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;
}