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

· · 题解

我是奶龙。

称序列 x_1 \sim x_{2m} 是优美的，当且仅当 \forall i \in [1,m], x_i+x_{i+m}=0。给定长为 n 的序列 a_i，求优美的子数组 a[l:r] 数目。

枚举 m=k 并将序列以 k 为块长定长分块，则优美区间恰好跨越两个关键点。关键点数目是调和级数的 O(n \log n)。

考察相邻关键点 x,y。设优美区间的起点 l=x-d，我们要求 x-d \sim x-d+k-1 和 y-d \sim y-d+k-1 相等。这里的相等定义为 \forall i, a_i=-b_i。

设 u=\text{lcp}(x,y) 和 v=\text{lcs}(x-1,y-1)。左边需要匹配 d 个元素，右边需要匹配 k-d 个元素，可列得约束：

解得 l 的范围是一段区间，统计贡献即可。

对于 u 的求解，可以将 a_i 取反拼到后面跑 SA，查询 v 只要取反串 SA。复杂度 O(n \log n)。

:::::info[代码]

const int N = 4e5 + 5;
int n, a[N];

struct suffix_array {
    int sa[2*N], rk[2*N], ht[N], rk0[N], cnt[N], id[N], st[20][N];
    void init(int* a, int n, int m) {
        fill(cnt + 1, cnt + m + 1, 0);
        for (int i = 1; i <= n; i++) cnt[rk[i] = a[i]]++;
        for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
        for (int k = 1, p = 0; p < n; k *= 2, m = p) {
            int c = 0;
            for (int i = n-k+1; i <= n; i++) id[++c] = i;
            for (int i = 1; i <= n; i++) if (sa[i] > k) id[++c] = sa[i] - k;
            fill(cnt + 1, cnt + m + 1, 0);
            for (int i = 1; i <= n; i++) cnt[rk[id[i]]]++;
            for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
            for (int i = n; i >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i];
            p = 0, copy(rk + 1, rk + n + 1, rk0 + 1);
            auto cmp = [&](int x, int y) {
                return rk0[x] == rk0[y] && rk0[x+k] == rk0[y+k];
            };
            for (int i = 1; i <= n; i++) rk[sa[i]] = cmp(sa[i-1], sa[i]) ? p : ++p;
        }
        for (int i = 1, j = 0; i <= n; i++) {
            if (rk[i] == 0) continue;
            for (j ? j-- : 0; a[i+j] == a[sa[rk[i]-1]+j]; ) j++;
            ht[rk[i]] = j;
        }
        copy(ht + 1, ht + n + 1, st[0] + 1);
        for (int i = 1; (1<<i) <= n; i++) 
            for (int j = 1; j + (1<<i) - 1 <= n; j++)
                st[i][j] = min(st[i-1][j], st[i-1][j + (1<<(i-1))]);
    }
    int ask(int l, int r) {
        if (l > r) swap(l, r);
        int k = lg(r - l++);
        return min(st[k][l], st[k][r - (1<<k) + 1]);
    }
} S, T;

int lcp(int x, int y) {
    return S.ask(S.rk[x], S.rk[y+n]);
}
int lcs(int x, int y) {
    if (x <= 0 || y <= 0) return 0;
    return T.ask(T.rk[n+1-x], T.rk[2*n+1-y]);
}

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    copy(a + 1, a + n + 1, a + n + 1);
    for (int i = n+1; i <= 2*n; i++) a[i] = -a[i];
    for (int i = 1; i <= 2*n; i++) a[i] += n;
    S.init(a, 2*n, 2*n);
    reverse(a + 1, a + 2*n + 1), T.init(a, 2*n, 2*n);
    i64 res = 0;
    for (int k = 1; k <= n/2; k++) 
        for (int x = k, y = 2*k; y <= n; x += k, y += k) {
            int u = lcp(x, y), v = lcs(x-1, y-1);
            int lo = max({0, x+2*k-n-1, k-u});
            int hi = min({k-1, x-1, v});
            if (lo <= hi) res += hi - lo + 1;
        }
    cout << res << '\n';
}

:::::