题解 | #中位数#

B题
https://ac.nowcoder.com/acm/contest/11177/B
提供一个我觉得比较清晰的思路，
只需要预处理出x两边有多少个数比它小，最后遍历一遍二分查询就行了。

直接拿样例举例：
5 3 2
1 2 3 4 5
d[3]=x。
我们可以预处理出：
l[]={2,1,0,0,0};表示下标i到下标3有多少个数比d[3]小。
r数组同理
不难发现两个数组单调。
最后只需要二分统计答案，对于l[i]=a的位置，有r[]中有多少数等于k-1-a。

代码

#include <bits/stdc++.h>

using namespace std;

#define fir(i, a, b) for (int i = (a); i <= (b); i++)
#define rif(i, a, b) for (int i = (a); i >= (b); i--)

const int N = 2e5 + 10;
int n, x, k, d[N], sub;
int l[N], r[N];
void init() {}
int main()
{
    scanf("%d%d%d", &n, &x, &k);
    fir(i, 1, n)
    {
        scanf("%d", &d[i]);
        if (d[i] == x)
            sub = i;
    }
    rif(i, sub, 1)
    {
        l[i] = l[i + 1] + (d[i] < x);
    }
    fir(i, sub, n)
    {
        r[i] = r[i - 1] + (d[i] < x);
    }
    LL ans = 0;
    fir(i, 1, sub)
    {
        ans+=(upper_bound(r + sub, r + n + 1, k - 1 - l[i]) - lower_bound(r + sub, r + n + 1, k - 1 - l[i]));
    }
    printf("%lld",ans);
    return 0;
}