题解：P17579 [JAG 2026 Summer Camp #3] Noise Cancelling

· · 题解

来个毛毛虫坐火箭做法。

以下记 R(s) 表示将序列 s 的每一位都取相反数得到的新序列，如 R(\{1, -1\}) = \{-1, 1\}。

对原题的结构做一些转化，实际上我们只需要对满足 i < j，\operatorname{lcp}(a[i, n], R(a[j, n])) \ge j-i 的二元组 (i, j) 计数即可。

拍到后缀数组上，对于排名为 i 的正串和排名为 j 的反串，若 i<j，则限制转为：

\min (\{h_i, h_{i+1}, \dots, h_{j-1}\}) \ge pos_j - pos_i, \qquad pos_j > pos_i

若 i>j，则左边那一项变为 \min (\{h_j, h_{j+1}, \dots, h_{i-1}\})。这两种情况是等价的，我们以下不妨先全部认为 i<j。

其中 h_i 表示 SA 上排名为 i, i+1 的两个后缀的 LCP，pos_i 表示排名为 i 的后缀对应的原串中的起点。

考虑记 k 表示 i,j 之间 h 数组的最小值。若有多个取最左侧的。那么反过来考虑，一个 k 能覆盖到的区间是可以二分出来的。

不妨先考虑 i<j 的情况。记当前 h_k 能覆盖到的区间是 [l, r]，那么有：

我们可以选 [l, k] 和 [k+1, r] 中区间长度小的那一边遍历，这样可以枚举到 i 或 j，转化为一个二维数点，可以主席树做。根据笛卡尔树的经典结论，这样做遍历的总次数是 O(n \log n) 级别。因此这部分的总复杂度是 O(n \log^2 n)。

实现中为了方便（因为是模拟赛考场代码）使用了二分哈希的两 \log 建 SA 方式。经过轻微卡常可以通过。

#include <bits/stdc++.h>
using namespace std;

#define ull unsigned long long
const int N = 5e5 + 5;
const ull base = 1313131;

int n, a[N], p[N * 2], h[N * 2], f[21][N * 2], lg[N * 2];
ull rd[N * 2], pw[N * 2], hs1[N * 2];
ull b1[N * 2];

bool tag[N];
long long ans = 0;

mt19937_64 rng(time(nullptr));

inline ull gethsh1(int l, int r)
{
    return hs1[r] - hs1[l - 1] * pw[r - l + 1];
}

inline int getlcp(int x, int y)
{
    int lenx = 2 * n - x + 1;
    int leny = 2 * n - y + 1;

    for(int i = 1; i <= 5; i++)
        if(b1[x + i - 1] != b1[y + i - 1]) return i - 1;

    int l = 1, r = min(lenx, leny), res = 0;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(gethsh1(x, x + mid - 1) == gethsh1(y, y + mid - 1))
            res = mid, l = mid + 1;
        else r = mid - 1;
    }

    return res;
}

bool cmp(int x, int y)
{
    int lenx = 2 * n - x + 1, leny = 2 * n - y + 1;
    int res = getlcp(x, y);
    if(res == lenx) return 1;
    if(res == leny) return 0;
    return b1[x + res] < b1[y + res];
}

int query(int l, int r)
{
    int x = lg[r - l + 1];
    return min(f[x][l], f[x][r - (1 << x) + 1]);
}

int root[N * 2], lc[N * 21 * 2], rc[N * 21 * 2], sum[N * 21 * 2], idx;

int update(int l, int r, int p, int x)
{
    int y = ++idx;
    lc[y] = lc[x], rc[y] = rc[x], sum[y] = sum[x] + 1;
    if(l == r) return y;
    int mid = (l + r) >> 1;
    if(p <= mid) lc[y] = update(l, mid, p, lc[y]);
    else rc[y] = update(mid + 1, r, p, rc[y]);
    return y;
}

int query(int l, int r, int L, int R, int x, int y)
{
    if(l > r || L > R) return 0;
    if(!y) return 0;
    if(L <= l && r <= R) return sum[y] - sum[x];
    int mid = (l + r) >> 1, res = 0;
    if(L <= mid) res += query(l, mid, L, R, lc[x], lc[y]);
    if(mid < R) res += query(mid + 1, r, L, R, rc[x], rc[y]);
    return res;
}

void solve()
{
    for(int i = 0; i <= idx; i++)
        lc[i] = rc[i] = sum[i] = 0;
    idx = 0;
    cin >> n;
    ans = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
        b1[i] = rd[a[i] + n], b1[i + n] = rd[-a[i] + n];
    for(int i = 1; i <= n * 2; i++)
        p[i] = i, hs1[i] = hs1[i - 1] * base + b1[i];
    for(int i = 2; i <= n * 2; i++) lg[i] = lg[i >> 1] + 1;
    sort(p + 1, p + n * 2 + 1, cmp);

    for(int i = 1; i <= n * 2 - 1; i++)
        h[i] = getlcp(p[i], p[i + 1]), f[0][i] = h[i];

    for(int j = 1; j <= 20; j++)
    for(int i = 1; i + (1 << j) - 1 <= n * 2 - 1; i++)
        f[j][i] = min(f[j - 1][i], f[j - 1][i + (1 << j - 1)]);

    for(int i = 1; i <= n * 2; i++)
        root[i] = update(1, n * 2, p[i], root[i - 1]);

    int cnt = 0;
    for(int k = 1; k < n * 2; k++)
    {
        int lt = k, rt = k + 1;

        int l = 1, r = k - 1;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(query(mid, k - 1) >= h[k]) lt = mid, r = mid - 1;
            else l = mid + 1;
        }

        l = k + 2, r = 2 * n;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(query(k + 1, mid - 1) > h[k]) rt = mid, l = mid + 1;
            else r = mid - 1;
        }

        if(k - lt + 1 <= rt - (k + 1) + 1)
        {
            for(int i = lt; i <= k; i++)
            {
                if(p[i] > n) continue;

                int L = p[i] + n + 1;
                int R = h[k] + p[i] + n;
                L = max(1, L);
                R = min(2 * n, R);

                if(L <= R)
                {
                    ans += query(1, n * 2, L, R, root[k], root[rt]);
                }
            }

            for(int j = lt; j <= k; j++)
            {
                if(p[j] <= n) continue;
                int R = p[j] - n - 1;
                int L = p[j] - n - h[k];
                L = max(1, L);
                R = min(2 * n, R);

                if(L <= R)
                {
                    ans += query(1, n * 2, L, R, root[k], root[rt]);
                }
            }
            continue;
        }
        else
        {
            for(int j = k + 1; j <= rt; j++)
            {
                if(p[j] <= n) continue;

                int R = p[j] - n - 1;
                int L = p[j] - n - h[k];
                L = max(1, L);
                R = min(2 * n, R);

                if(L <= R)
                {
                    ans += query(1, n * 2, L, R, root[lt - 1], root[k]);
                }
            }

            for(int i = k + 1; i <= rt; i++)
            {
                if(p[i] > n) continue;

                int L = p[i] + n + 1;
                int R = h[k] + p[i] + n;
                L = max(1, L);
                R = min(2 * n, R);

                if(L <= R)
                {
                    ans += query(1, n * 2, L, R, root[lt - 1], root[k]);
                }
            }           
        }
    }
    cout << ans << '\n';
    return;
}

int main()
{
    pw[0] = 1;
    for(int i = 0; i <= N * 2 - 1; i++) rd[i] = rng();
    for(int i = 1; i <= N * 2 - 1; i++) pw[i] = pw[i - 1] * base;
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}