题解 | #k小数查询#

B题
我们可以预先处理出所有小于 x 的值，给当前位置 pre[i] 加上 1 ，然后处理出前缀和，可以通过前缀和的差值知道每个区间的小于 x 的值的数量，对于 i 位置的pre[i] 一定需要一个pre[i] + k - 1 才能保证该区间的 < x 的数量刚好为k - 1,可以通过二分查找到最大位置和最小位置， 然后对于 x 所对应的位置 pos 一定要包含在内 ，判断一下即可。

#include<bits/stdc++.h>
using namespace std;
#define maxn 200005

int a[maxn];
int pre[maxn];

int main(){
    int n, x, k;
    scanf("%d%d%d",&n,&x,&k);
    int ans = 0, pos;
    for(int i = 1;i <= n;i++){
        scanf("%d",&a[i]);
        if(a[i] < x) pre[i]++;
        if(a[i] == x) pos = i;
    }
    for(int i = 1;i <= n;i++){
        pre[i] += pre[i - 1];
    }
    for(int i = 0;i <= pos - 1;i++){
        int pos1 = lower_bound(pre + 1,pre + 1 + n, pre[i] + k - 1) - pre;
        int pos2 = upper_bound(pre + 1,pre + 1 + n, pre[i] + k - 1) - pre;
        if(pos1 > pos && pos2 > pos)  ans += abs(pos2 - pos1);
        if(pos2 > pos && pos1 < pos)  ans += abs(pos2 - pos);
    }
    printf("%d\n",ans);
}