2023牛客+杭电补题和总结记录（后半）

Chloris_Black / 2023-08-08 / 原文

前半继续写要被编辑器卡飞了，换个档

杭电第六场

\(1002.Pair\ Sum\ and\ Perfect\ Square\)
对于每个位置可以求出该位置的数和哪些位置的数能够组成完全平方数，因为原序列是排列，并且完全平方数个数不多，所以预处理的复杂度不高。（也可以在后续统计过程中处理）
处理出点对以后就变成了二维数点问题。我一开始把所有询问拆成两个端点排序，这样复杂度会基于 \(2*q\)。后来经大佬提点后领悟了，直接对右端点排序，从 \(1\) 处理到 \(n\) 的过程中只需要对于每个位置在树状数组中加进另一个数比自己小的点对，然后在查询时一样用右端点的查询减去左端点-1的查询。此时因为每个位置只有另一维比自己小的点对，矩形区域相减减去了下边多出来的部分，而左边的部分本来就是空的，这样保证了正确性。

Pair Sum and Perfect Square

#include
using namespace std;
const int N = 1e5 + 10;
int t, n, a[N], rec[N], m, ans[N], tree[N], vis[N];
struct node {
    int id, l, r;
}q[N];
inline bool cmp(node x, node y) {
    return x.r == y.r ? x.l < y.l : x.r < y.r;
}
inline void add(int x) {
    for (;x <= n;x += (x & -x))tree[x]++;
}
inline int query(int x) {
    int val = 0;
    for (;x;x -= (x & -x))val += tree[x];
    return val;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1;i <= n;i++) {
            cin >> a[i];
            rec[a[i]] = i;
            tree[i] = 0;
            vis[i] = 0;
        }
        cin >> m;
        for (int i = 1;i <= m;i++) {
            ans[i] = 0;
            cin >> q[i].l >> q[i].r;
            q[i].id = i;
        }
        sort(q + 1, q + m + 1, cmp);
        int tag = 1;
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j * j <= 2 * n;j++) {
                int y = j * j;
                if (y - a[i] > 0 && y - a[i] <= n && vis[rec[y - a[i]]]) {
                    add(rec[y - a[i]]);
                }
            }
            while (q[tag].r <= i && tag <= m) {
                ans[q[tag].id] = query(q[tag].r) - query(q[tag].l - 1);
                tag++;
            }
            vis[i] = 1;
        }
        for (int i = 1;i <= m;i++)cout << ans[i] << '\n';
    }
    return 0;
}