CF1079 D 题解 - dk-qwq blog

D. Another Problem about Beautiful Pairs #

题意#

给定一个长度为 $n$ 的数组 $a$ ，统计满足 $a_i a_j = j - i$ 的 $(i, j)$ 数对的数量

题解#

显然有枚举 $a_j$ 的算法，然后 check $j = i + a_i * a_j$ 处是否满足 $a_j$ 的值，复杂度 $\Omicron \left( \sum \frac n {a_i} \right)$

瓶颈显然在 $a_i$ 较小的时候

不妨考虑根号分治，令 $B = \lfloor\sqrt{n}\rfloor$

对于 $a_i \gt B$ 的情况，直接枚举 $a_j$ 即可，复杂度 $\Omicron (\frac n B)$

由于 $a_i \gt B$ 与 $a_j \gt B$ 的情况不能被同时满足，不需要考虑重叠

对于 $a_i \leq B$ ， $a_j > B$ 情况已经被前面统计，枚举 $a_j \leq B$ 即可，复杂度 $\Omicron (B)$

存在重复考虑的情况，只向一个方向统计

总复杂度 $\Omicron (n (B + \frac n B)) = \Omicron (n\sqrt{n})$ ，提交记录

34 collapsed lines
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
ll n, a[N];
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int B = 1;
    while((B + 1) * (B + 1) <= n) B++;

    ll res = 0;
    for(ll i = 1; i <= n; i++) {
        if(a[i] <= B) {
            for(ll j = 1; j <= B; j++)
                if(i + a[i] * j <= n && a[i + a[i] * j] == j) res++;
        } else {
            for(ll j = 1; j <= B + 1; j++) {
                if(i - a[i] * j > 0 && a[i - a[i] * j] == j) res++;
                if(i + a[i] * j <= n && a[i + a[i] * j] == j) res++;
            }
        }
    }
    cout << res << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    // freopen("A.in", "r", stdin);
    // freopen("A.out", "w", stdout);
    int T = 1;
    cin >> T;
    while(T--) solve();
}

D. Another Problem about Beautiful Pairs#

题意#

题解#

D. Another Problem about Beautiful Pairs #