题目

题解

这边只展开讲解 Hard 版本，题目将给定一个长度为 $n$ 的数组 $a$，并给定 $k$ 次询问，每次询问给定一个值 $d$ 要求我们回答 $a$ 中有多少个元素严格大于 $d$，有多少个元素严格小于 $d$。

首先我们观察题目的数据范围 $n$ 的最大值可达 $5 \times 10^6$，显然这个数据范围是不想要我们使用二分 / 排序解决这道题的，因为排序或者二分的时间复杂度均为 $O(N\log N)$ 显然在该题的极端数据下会超时（但是实际上数据并不会达到极端值，因为洛谷不允许上传超过 50 Mb 的数据包），如果有人想用暴力的方法直接在每次查询时遍历数组，显然更无法在该题的时间限制下通过本题，这个方法的时间复杂度为 $O(N \times K)$，$k$ 的最大值为 $5 \times 10^6$，显然会大幅度超过 $10^8$ 次循环（相当于 1s）。

因此这里给大家介绍一种数据结构，即 ‘前缀和’，前缀和是一种以 $O(1)$ 的时间复杂度查询数据，以 $O(N)$ 的时间复杂度构建且不支持修改数据的数据结构（若要修改数据，则必须重新构建），显然这道题不需要修改数据，后续 $k$ 次询问均为查询数据，假设一个场景（大家注意下标范围，这里不会对下标范围进行解释，大家自行理解）：现在有一个长度为 $n$ 的数组 $b$，我们需要快速统计 $b$ 的前 $i$ 个元素的和，中途不会修改 $b$ 数组的元素。前缀和就是最适合这种场景的数据结构，具体来说我们声明一个数组 $c$，对于任何下标 $x$ 我们需要让 $c[x]$ 的值等于 $\sum^{x}_{i = 0}{b_i}$，实现方法很简单，我们只需要注意到一个递推关系：$c[i + 1] = c[i] + b[i + 1]$，那么显然我们只需要根据这个递推关系就能以 $O(N)$（循环 $n$ 次) 的时间复杂度成功构建前缀和数组，这里容易出现越界问题，我们可以同时让二者的长度增加一个，空出来的元素令为 $0$ 就可以自动处理越界问题了。

c[0] = 0;
for (int i = 0; i <= n - 2; ++i)
{
    c[i + 1] = c[i] + b[i + 1];
}

那么具体如何使用 ‘前缀和’ 解决这道题呢？实际上题目里有一个隐式的求和关系，我们假设出一个新的数组 $cnt$，它和原数组 $a$ 的关系为 $cnt[i] = a$ 中值为 $i$ 的元素的个数，假设 $a = {4, 2, 2, 1}$ 那么 $cnt[0] = 0$, $cnt[1] = 1$, $cnt[2] = 2$, $cnt[3] = 0$, $cnt[4] = 1$，那么若给定值 $d$，$a$ 中严格小于 $d$ 的元素个数即为 $\sum_{i = 0}^{d – 1} {cnt_i}$，设 a 中元素的最大值为 $mx$，严格大于 $d$ 的元素个数即为 $\sum_{i = 0}^{mx}{cnt[i]} – \sum_{i = 0}^{d}{cnt[i]}$，这边再给大家提醒一个点，即 cnt 数组的长度应该开多大？由于我们的 cnt 实际储存的是 a 中可能出现的元素的值，因此 cnt 的长度应该由 $a_i$ 的值域决定，可以直接开 $10^7$ 大小，最好开 $10^7 + 1$ 大小，前缀和数组的长度与 cnt 数组的长度设为相同，前者需要你们在代码中小心处理潜在的越界风险，后者则更为方便，可以避免大多数越界问题。

在使用前缀和时非常容易出现越界问题，这里总结一个通用方法，我们提前分清两个名词对应的对象 ‘被前缀和数组’ 及 ‘前缀和数组’，假设被前缀和的数组题目给定长度为 $n$，那么我们实际将二者的长度开为 $n + 1$，并在进行递推时将前缀和数组处理到第 n 个元素为止。

最后再提一下 C++ 的快读快写，如果想使用 C++ 的输入输出解决本题，最好看一下。

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

#include <bits/stdc++.h>

using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;

const int MAXN = 1e7 + 1;

// 全局数组会自动初始化元素初始值为 0
int cnt[MAXN + 1];
int pref[MAXN + 1];

void solve()
{
    int n, k; cin >> n >> k;
    for (int i = 0; i < n; ++i)
    {
        int num; cin >> num;
        cnt[num]++;
    }

    // 处理到 MAXN 为止，如果采取递推 pref[i] = pref[i - 1] + cnt[i] 则 i 应该从 1 开始，处理到 MAXN （而非 MAXN - 1 为止）
    for (int i = 0; i < MAXN; ++i)
    {
        pref[i + 1] = pref[i] + cnt[i + 1];
    }


    while (k--)
    {
        int d; cin >> d;
        cout << pref[MAXN] - pref[d] << ' ' << pref[d - 1] << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;

    while (t--)
    {
        solve();
    }
}