题解：AT_abc417_c [ABC417C] Distance Indicators

推式子后的结论题。

我们把式子变形：$j-i=A_i+A_j$ 变为 $A_i+i=j-A_j$，其中 $A_i+i$ 和 $j-A_j$ 都是可以很快速得到的。

于是我们考虑用一个桶记录每一个数字出现的频次，见代码：

#include <cstdio>
int a[200005], tong[400005];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), ++tong[a[i] + i];
    long long ans = 0;
    for (int i = 1; i <= n; ++i) if (i - a[i] >= 0) ans += tong[i - a[i]];
    printf("%lld", ans);
}

下面是对这个代码的解释：

1. 题目要求 $i < j$，上面的方法会不会导致出现 $i \geq j$ 的情况出现？

   不会的。题目保证 $1 \leq A_i$，因此： $$ i-A_i < j(i < j) $$ 也就是说，上面的累加过程只会匹配到在 $i$ 前面的数字，这样就可以保证题目要求能完成。

2. 桶要开多大？考虑极端情况 $2 \times 10^5 + 2 \times 10^5=4 \times 10^5$。

3. 要开 long long。可以看后面的小节。

4. 代码的时间复杂度显然为 $O(N)$，空间复杂度为 $O(N+W)$（$W$ 为值域）。

为什么要开 long long？

考虑极端数据：前两项为 $1$，后面有 $A_i=A_{i-1}+1$（可得最后一项为 $2 \times 10^5-1$）。这样两两相加可以构造出 $\left[2,2 \times 10^5\right]$ 内的所有整数，于是：

数对总数为 $\frac{N(N-1)}{2}=10^5 \times (2 \times 10^5-1)=2 \times 10^{10} - 10^5$（下文记为 $t$）。

$(i,j)$ 中 $j-i=1$ 的数对数量为 $10^5-1$。

$(i,j)$ 中 $2 \leq j-i \leq 2 \times 10^5$ 的数对数量为 $t-(10^5-1)=2 \times (10^{10}-10^5)+1 > 2^{31}-1$。超出 int 范围。