2021CCPC小凯的书架

树状数组 在线处理序列中比k大的数量 T4 小凯看到小辣如此的卷，于是他买了很多本书，决定也开始卷。

小凯的书架上有 $n$ 本书，从左到右第 $i$ 本书的高度为 $a_i$ ，对于所有 $i\in [1,n]$ ，求第 $i$ 本书往左第 $k$ 本比第 $i$ 本书高的书的高度，如果不存在这样的书，请输出 $-1$。

输入

第一行一个正整数 $T$, 表示数据组数。

对于每组数据：

第一行输入两个正整数 $n$ 和 $k$ 。

第二行输入 $n$ 个正整数 $a_i$ ，表示每本书的高度。

数据保证 $1\le n\le 10^5，\sum n\le 3\ast 10^5，1\le k\le 50，1\le a_i\le 10^9$ ，数据保证所有书本的高度在 $[1,10^9]$ 内随机生成。

输出

对于每组数据输出 $n$ 行，第 $i$ 行输出第 $i$ 本书往左第 $k$ 本比第 $i$ 本书高的书的高度，如果不存在这样的书，请输出 $-1$。

样例输入

1
10 3
852273206 148560760 979303226 716148781 133605412 464797992 315860976 653152358 898884753 545164585

样例输出

-1
-1
-1
-1
148560760
852273206
979303226
852273206
-1
716148781

思路

参考博客

从一个乱序数组中, 找从数 $a_i$ 起往左第 $k$ 个 $a_j>a_i$ 的数 $a_j$。

有一个类似的问题：从 $[1,i-1]$ 中找第 $k$ 个 $a_j>a_i$ 的 $a_j$ , 这个问题可以用以数值组织的树状数组+二分解决。

而这里需要保证找到的数是在原数组中从 $a_i$ 往左第 $k$ 个大于 $a_i$ 的数。得找到一种关系, 使得既能快速找到第 $k$ 个大于 $a_i$ 的数, 又能满足是往左数的。

可以定义一个数组 $i{d}_i$,记录原数组中每个元素的下标, 然后依据原$A$数组给下标数组$id$ 从大到小排序：

sort(id + 1, id + n + 1,[&](int i,int j){ // C++的匿名函数
	return a[i] > a[j];
});

此时的 $id$ 数组数值上保存的是原数组下标, 位置却是满足从大到小的关系, 即当你确定一个数 $i{d}_i$ 时, $1\sim i-1$ 中对应的原数组值都大于当前的值。

回忆一下之前提到的类似的问题, 之前的解法中是利用插入的先后顺序来确保此时树状数组中的值都是在当前值之前, 才能用二分计数前缀和得出 $[1,i-1]$ 的 第$k$大数。

而我们从大到小插入$i{d}_i$时, 树状数组区间是 $i{d}_i$ 的值, 插入顺序又满足原数组从大到小的顺序, 即先插入的数都要比后插入的数大, 因此 $sum(i{d}_i)$ 的值（add前）就是 原数组$a[i{d}_i]$ 左边 $>a[i{d}_i]$ 的数的个数, 且是对应原数组下标的顺序。

此时再进行二分 $1\sim i{d}_i$ 时, 就是在满足 $a_j>a_i$ 且 $j<i$ 两个条件内中搜索, 直接找对应的 $sum(i{d}_i)-k+1$ 就是要找的数。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <unordered_map>
#include <vector>
using namespace std;
const int N = 4e5 + 10;
int a[N];
int n, m, k;
int t[N], id[N];
int ans[N];
 
bool cmp(int &i, int &j)
{
    return a[i] > a[j];
}
 
int lowbit(int x)
{
    return x & -x;
}
 
void add(int x)
{
    for (int i = x; i < N; i += lowbit(i))
        t[i]++;
}
 
int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += t[i];
    return res;
}
 
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        n = 0;
        memset(t, 0, sizeof t);
        cin >> m >> k;
        vector<int> nums;
        for (int i = 1; i <= m; i++)
        {
            cin >> a[i];
            id[i] = i;
        }
        sort(id + 1, id + m + 1, cmp);
 
        for (int i = 1; i <= m; i++)
        {
            int x = id[i];
            if (sum(x) < k)
            {
                add(x);
                ans[x] = -1;
                // cout << -1 << " ";
                continue;
            }
            int cnt = sum(x), l = -1, r = x - 1;
            while (l != r - 1)
            {
                int mid = l + r >> 1;
                if (sum(mid) < cnt - k + 1)
                    l = mid;
                else
                    r = mid;
            }
            ans[x] = a[r];
            add(x);
        }
        for (int i = 1; i <= m; i++)
            cout << ans[i] << "\n";
        // printf("DEBUG\n");
    }
    return 0;
}