题目描述

难度分:$1200$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$，$q$ 之和$\leq 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$、$q(1 \leq q \leq 10^5)$和长为$n$的严格递增数组$a(1 \leq a[i] \leq 10^9)$。

对于每个满足$i \lt j$的$(i,j)$，画一条线段（闭区间）$[a_i,a_j]$。一共有$\frac{n \times (n-1)}{2}$条线段。

然后输入$q$个询问，每个询问输入$k(1 \leq k \leq 10^{18})$，输出有多少个整数恰好在$k$条线段中。

输入样例

3
2 2
101 200
2 1
6 15
1 2 3 5 6 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
5 8
254618033 265675151 461318786 557391198 848083778
6 9 15 10 6 9 4 4294967300

输出样例

0 100 
0 0 0 0 2 0 0 0 3 0 2 0 0 0 0 
291716045 0 0 0 291716045 0 301749698 0 

算法

组合

对于区间$(a_{i-1},a_i)$内部的点，可以被$(i-1) \times (n-i+1)$条线段覆盖，即线段左端点可以是$[1,i-1]$，右端点可以是$[i,n]$。而对于每个$a[i]$，可以被$i \times (n-i+1)-1$条线段覆盖，即左端点可以是$[1,i]$，右端点可以是$[i,n]$，但是要去掉一个没有长度，仅包含一个点的线段。

遍历$a$数组，构建出一个映射表$counter$，表示“出现次数$\rightarrow$点的数量”。然后处理每个询问都查表即可。

复杂度分析

时间复杂度

遍历一遍数组$a$，预处理出$counter$的时间复杂度为$O(n)$。然后处理每个询问都是查表，每次查询的时间复杂度为$O(1)$，总的时间复杂度为$O(q)$。因此，整个算法的时间复杂度为$O(n+q)$。

空间复杂度

空间消耗主要在于映射表$counter$，由于$i$和$n-i$此消彼长，两者之和是$O(n)$，一旦$i \gt \sqrt{n}$就会开始重复。因此$counter$中的键值对数量大概是$O(\sqrt{n})$，这也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010;
int t, n, q, a[N];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &q);
        unordered_map<LL, LL, custom_hash> counter;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if(i > 1 && a[i - 1] + 1 < a[i]) {
                counter[(i - 1LL) * (n - i + 1)] += a[i] - a[i - 1] - 1;
            }
            counter[1LL * i * (n - i + 1) - 1]++;
        }
        while(q--) {
            LL k;
            scanf("%lld", &k);
            printf("%lld ", counter.count(k)? counter[k]: 0);
        }
        puts("");
    }
    return 0;
}