2314. 魔法森林的“差值默契”挑战
1000ms
256MB
简单
枚举算法
二分算法
题目描述
在神秘的魔法森林里，居住着 $N$ 只拥有不同魔力值的精灵。为了准备即将到来的“森林默契大赛”，精灵女王下达了一个挑战：
给定一个目标差值 $C$，精灵们需要找出森林中所有满足“魔力值之差刚好等于 $C$”的精灵对。
规则如下：
1. **差值契合**：如果精灵 A 的魔力值减去精灵 B 的魔力值刚好等于 $C$（即 $A - B = C$），那么它们就是一对“默契搭档”。
2. **位置区分**：森林里的精灵都有自己的编号，即使两只精灵的魔力值相同，只要它们在队伍中的位置不同，就视作不同的个体。因此，不同位置的数字构成的数对算作不同的数对。
请你编写一个程序，帮精灵女王统计一下，森林里一共有多少对这样的“默契搭档”？
输入格式
- 第一行包含两个正整数 $N$ 和 $C$ ($1 \le N \le 2 \times 10^5, \quad 1 \le C \lt 2^{30}$)，分别表示精灵的总数和目标差值。
- 第二行包含 $N$ 个正整数 $a_i$ ($0 \le a_i \lt 2^{30}$)，表示这 $N$ 只精灵各自的魔力值。
输出格式
- 输出一行一个整数，表示满足 $A - B = C$ 的“默契搭档”总数。
样例 1
输入 (Input)
4 1 1 1 2 3
输出 (Output)
3
- 对于 $75\%$ 的数据：$1 \le N \le 2000$。
- 对于 $100\%$ 的数据：$1 \le N \le 2 \times 10^5, \quad 0 \le a_i \lt 2^{30}, \quad 1 \le C \lt 2^{30}$。
- **样例说明**：
精灵魔力值序列为 `1 1 2 3`，目标差值 $C = 1$。
满足条件的数对有：
- (2, 第一个1)
- (2, 第二个1)
- (3, 2)
共 3 对。
- **算法提示**：
由于 $N$ 较大，暴力枚举 $O(N^2)$ 会超时。建议将公式变形为 $A = B + C$，利用哈希表（如 `std::map`）记录每个魔力值出现的频次，遍历每个 $B$ 并查找对应的 $A$ 是否存在。
- **注意**：最终结果可能超过 `int` 范围，请使用 `long long` 存储。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功