题解：AT_abc417_c [ABC417C] Distance Indicators

说在前面

前置芝士：扫描线。

题目分析

题目让我们求满足当 $j > i$ 时 $j - i = a _ i + a _ j$ 的 $(i, j)$ 的个数，如果直接枚举的话，时间复杂度是 $O(n ^2)$ 的，无法接受。

如何优化？

优化

我们发现，可以对于所有的 $i$，求出满足条件的 $j$ 的个数，最后把所有的满足条件的 $j$ 的个数加起来即可得到答案。

公式推导

那么我们如何求满足条件的 $j$ 的个数呢？

首先我们拿到原式： $$ j - i = a _ i + a _ j $$ 由于我们的 $i$ 是已知的，所以我们把和 $i$ 有关的都放在一边： $$ a _ i + i = j - a _ j $$ 那么满足条件的 $j$ 的数量，就是对于所有 $j > i$ 满足 $j - a _ j = a _ i + i$ 的数量。

那么这个东西我们怎么去统计呢？

我们倒序扫描（因为 $i$ 的信息是从 $j$ 来的），每次先查询 $a _ i + i$ 的个数，再将 $i - a _ i$ 的个数增加 $1$。

注意：先查询的原因是：$j > i$，不能取到 $i$ 的贡献。

这样，每次查询时我们就能快捷的知道所有满足条件的 $j$ 的数量了。

这个算法就叫扫描线，是不是很像模拟了一根线在扫描？

至此，讲解结束，时间复杂度 $O(n \log n)$（后面会讲为什么是 $n \log n$）。

注意事项

1. $i - a _ i$ 可能是负的，要用 map 或者加上偏移量转正，但是由于 $a _ i + i$ 是正的，所以 $i - a _ i$ 如果是负的就不用加一。由于本人比较懒，所以使用了 map。
2. map 自带 $\log n$。

完整代码

#include <bits/stdc++.h>

#define int long long
#define endl "\n"

using namespace std;

namespace zcq_qwq {
    const int N = 200000 + 5;

    int a[N];

    map<int, int> mp;

    int n;

    void main() {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        int ans = 0;
        for (int i = n; i >= 1; i--) {
            ans += mp[a[i] + i];
            mp[i - a[i]]++;
        }
        cout << ans;
    }
}

signed main() {
    zcq_qwq::main();
    return 0;
}

说在后面

若代码、思路讲解有误，欢迎提出！