题解：P15696 [2018 KAIST RUN Spring] QueryreuQ

___Mitsui_Hisashi___ · 2026-04-25 15:06:24 · 题解

Analysis

观察【数据范围】可知，q \le 10^4 妥妥的 \mathcal O(q^2)，即每次 \mathcal O(\vert s\vert)，所以我们会惊奇地发现我们需要用 Manacher。

模板如下：

for (int i = 1; i < n - 1; i++) {
    p[i] = i < r ? min(r - i, p[2 * mid - i]) : 1;
    while (t[i + p[i]] == t[i - p[i]])
        p[i]++;
    if (i + p[i] > r)
        r = i + p[i], mid = i;
    ans = max(ans, p[i] - 1);
}

那怎么计算回文子串的数量呢？其实就是 \sum\limits_{i=1}^{n-1} \lfloor \frac{p_i}{2}\rfloor。这也很好理解，我们设回文串的长度为 l，则 l = p_i - 1，对 l 的奇偶性进行分类讨论：

得证。

Manacher 部分如下：

for (int i = 1; i < n - 1; i++) {
    p[i] = i < r ? min(r - i, p[2 * mid - i]) : 1;
    while (t[i + p[i]] == t[i - p[i]])
        p[i]++;
    if (i + p[i] > r)
        r = i + p[i], mid = i;
    sum += p[i] / 2;
}

Code

#include"bits/stdc++.h"
using namespace std;
const int N = 2e4 + 5;
int q;
string s, t, op;
int p[N], mid, r;
int manacher() {
    mid = r = 0;
    t = "@ ";
    for (char c : s)
        t += c, t += " ";
    t += "~";
    int n = t.size(), sum = 0;
    for (int i = 1; i < n - 1; i++) {
        p[i] = i < r ? min(r - i, p[2 * mid - i]) : 1;
        while (t[i + p[i]] == t[i - p[i]])
            p[i]++;
        if (i + p[i] > r)
            r = i + p[i], mid = i;
        sum += p[i] / 2;
    }
    return sum;
}
signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin >> q >> op;
    for (int i = 0; i < q; i++) {
        if (isalpha(op[i]))
            s += op[i];
        else
            s.pop_back();
        cout << manacher() << ' ';
    }
    return 0;
}