题解 | #k小数查询#

题目大意：

给出长度为的序列 ，

有多少对不同的整数对满足且中第小的数是？

思路：

因为题目规定是一个排列，所以第k小数(设他为x)一定是唯一的（讲了跟没讲一样）
考虑预处理出对于x左右两边的比他小的数有多少个，分别记为s[i]对于位置i前面有多少个比x小的数，
e[i]表示对于位置i后面有多少个比x小的数。
考虑第k小，转换一下就是有个数小于x。

那我们就枚举S[i]前面比他小的数，再找后面有多少个位置j符合,
那符合条件的位置数就是答案（用f[i]表示前面取了A个，后面还要取i个的方案数）。

Code:

#include <cstdio>
#include <iostream>
#define ll long long

using namespace std;

const int N = 2e7 + 10;
ll s[N], e[N], f[N], ans, id, n, a[N], x, k;

int main()
{
    scanf("%lld%lld%lld", &n, &x, &k);
    for(ll i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        if(a[i] == x) id = i;
    }
    f[0] = 1;
    for(int i = id - 1; i >= 1; i--) s[i] = s[i + 1] + (a[i] < a[id]); //前面有多少个比他小
    for(int i = id + 1; i <= n; i++)
    {
        e[i] = e[i - 1] + (a[i] < a[id]);  //后面有多少个比他小
        f[e[i]]++;  //后面e[i]个的方案数
    }
    for(int i = 1; i <= id; i++) ans += f[k - s[i] - 1];  //统计答案
    printf("%lld\n", ans);
    return 0;
} 

:对于本题数据的虚假，题目上数据范围在2e6之内，但是这样交上去会WA,需要2e7才可以通过（罚时的快乐）