题解 | #k小数查询# 牛客练习赛87

B题让我们计算满足 x是区间第K小数的区间个数，就是找有k-1个数小于X的区间。由于区间必定包含X，我们从X开始向左右拓展，计算一下向左/右拓展m个数时对k-1的贡献，存入map计算数量，然后合并左右区间（乘法原理）。答案加上L[d]*R[k-1-d]。别忘记左右单独拓展的贡献，最后特判一下k=1的情况，X一个数时本身就是第1小的数字，答案+1。

#include<bits/stdc++.h>
const int N = 200005;
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
unordered_map<int, int> L;
unordered_map<int, int> R;
int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, x, k;
    cin >> n >> x >> k;
    int pos;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (x == a[i])
            pos = i;
    }
    int cnt = 0;
    ll ans = 0;
    //区间内有k-1个比x小的数
    for (int i = pos - 1; i >= 1; i--)
    {
        if (a[i] < x)
            cnt++;
        L[cnt]++;
        if (cnt == k - 1)//左
            ans++;
    }
    cnt = 0;
    for (int i = pos + 1; i <= n; i++)
    {
        if (a[i] < x)
            cnt++;
        R[cnt]++;
        if (cnt == k - 1)//右
            ans++;
    }
    for (auto v : L)
    {
        int kk = v.first;
        if (kk > k - 1)
            continue;
        ans += v.second * R[k - 1 - kk];//左右
    }
    if (k == 1)//本身
        ans++;
    cout << ans << endl;
    return 0;
}

.