Codeforces Round 975 (Div. 2) B. All Pairs Segments（组合数学）

题目链接：题目

大意：

给出一个数组，数字两两之间能组成一个闭区间，给出若干次查询，问恰好包含于$k$个区间的数有多少。

思路：

任意两数之间都能组成区间，那么我们要做的绝对不是遍历这些区间，因为复杂度过高，应该是用数学方法分析。$k$的范围很大，所以不是对每个$k$展开分析，而是对数组中的各个数字分析，将得出的答案存储起来，以供查询。
观察题目，数组中已给出的数字和两两之间的数字一定是要分开讨论的。对于已给出的数字来说，只要边界$l$在它左边（或自身），边界$r$在它右边（或自身），那么这个区间就能包含这个数；对于两两之间的数也是类似的，只是它们不会成为边界。然后将结果用哈希表储存起来，方便查询。

代码：

#include <bits/stdc++.h>
using namespace std;#define int long long
#define MOD 1000000007
#define fi first
#define se second
#define pii pair<int,int>
#define vec vectorvoid solve(){int n, q;cin >> n >> q;vec<int> x(n + 1);for(int i = 1; i <= n; i++){cin >> x[i];}vec<int> k(q);for(int i = 0; i < q; i++){cin >> k[i];}unordered_map<int, int> mp;for(int i = 1; i <= n; i++){mp[(i - 1) * (n - i) + i - 1 + n - i]++;}for(int i = 2; i <= n; i++){mp[(i - 1) * (n - i + 1)] += (x[i] - x[i - 1] - 1);}for(int i = 0; i < q; i++){cout << mp[k[i]] << ' ';}//cout << mp[1];cout << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin >> t;while(t--){solve();}return 0;
}