在做小学期Day5C题 (在线维护中位数) 时, 由于我没有做过, 也没有想到正解 (对顶堆) , 卡了很久, 最后用一个奇怪的方法做出来了。发现这个奇怪的做法复杂度稍高, 但是可以扩展。对顶堆只能维护中位数或固定k的第k大数, 而奇怪做法可以 (伪? ) 在线查找第k大数, k可变, 代价是$O(\log^2 n)$的, $n$为数列长度。
步入正题。
开始为空的一个数列, 有两种操作:
- 向数列中加入一个元素a
- 输入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;
}