「解题报告」CF1738H Palindrome Addicts

神秘回文串题。

首先容易发现要求的是区间本质不同回文串个数，所以直接上论文做法即可。

容易想到增量构建回文自动机，假如现在建出了 \([1, r]\) 的 PAM，考虑有多少回文串出现在了 \([l, r]\) 内。考虑记录每个回文串的最后一次出现位置 \(last_p\)，那么这个串的左端点就是 \(last_p - len_p + 1\)，也就是需要满足 \(last_p \ge l + len_p - 1\) 那么这个回文串就会造成贡献。

考虑每次插入一个字符时，找到当前的最长的回文串节点后，我们要更新的 \(last_p\) 实际上就是当前节点到根的每一个节点。直接维护好像不是很好维护，我们先观察下性质。根据 PAM 的构造过程容易发现，每拓展一次之后最多只增加一个本质不同的回文串，同理，删除一个字符之后也就最多减少一个本质不同回文串，那么我们其实只需要知道被删除的这一个回文串是哪个就行了。而又容易发现，这个回文串一定满足左端点 \(=l\)，且没有任何以它为前缀的更长的回文串（否则这个串一定出现不止一次），也就是在 \(fail\) 树上它是叶子。我们每次删除只删除一个叶子，那么修改的时候实际上也就不需要修改整条链了，只需要给链底打个标记，当这个节点成为叶子被删除后再将标记往上传。整个过程是均摊 \(O(n)\) 的。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000006;
int n;
char s[MAXN];
char op[20];
int ans;
struct PalindromeAutomaton {
    int t[MAXN][26], fail[MAXN], len[MAXN];
    int tag[MAXN], deg[MAXN];
    vector<int> e[MAXN];
    int tot, now;
    PalindromeAutomaton() {
        fail[0] = fail[1] = 1, len[1] = -1;
        tot = 1, now = 0;
    }
    void insert(int c, int pos) {
        int p = now;
        while (s[pos - len[p] - 1] != s[pos]) p = fail[p];
        if (!t[p][c]) {
            int np = ++tot;
            int q = fail[p];
            while (s[pos - len[q] - 1] != s[pos]) q = fail[q];
            fail[np] = t[q][c], len[np] = len[p] + 2, t[p][c] = np;
        }
        now = t[p][c];
    }
    void pushTag(int p, int v) {
        if (p > 1) {
            if (tag[p] == 0) ans++, deg[fail[p]]++;
            if (tag[p] < v) tag[p] = v, e[v - len[p] + 1].push_back(p);
        }
    }
    int jump(int p, int l) {
        while (len[p] > l) p = fail[p];
        return p;
    }
} pam;
int main() {
    scanf("%d", &n);
    int l = 1, r = 0;
    while (n--) {
        scanf("%s", op);
        if (op[1] == 'u') {
            scanf(" %c", &s[++r]);
            pam.insert(s[r] - 'a', r);
            pam.now = pam.jump(pam.now, r - l + 1);
            pam.pushTag(pam.now, r);
        } else {
            for (int p : pam.e[l]) {
                if (pam.tag[p] == l + pam.len[p] - 1 && pam.deg[p] == 0) {
                    pam.pushTag(pam.fail[p], pam.tag[p]);
                    pam.deg[pam.fail[p]]--, ans--, pam.tag[p] = 0;
                }
            }
            l++;
        }
        printf("%d\n", ans);
    }
    return 0;
}