神秘回文串题。
首先容易发现要求的是区间本质不同回文串个数，所以直接上论文做法即可。
容易想到增量构建回文自动机，假如现在建出了 \([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;
}