CF1738H Palindrome Addicts

题意

初始有一个空字符串 \(s\)。给定 \(q\) 组操作，每次操作是在 \(s\) 后加一个字符或是在 \(s\) 前删一个字符。每次操作后要输出 \(s\) 中本质不同回文子串数。

数据范围：\(n \le 10^6\)。

题解

这里提供一个在线好写的线性做法。

考虑把 LOJ6070 贺上去 我们显然要维护一个 PAM。再维护一个 \(cov\) 数组表示最后一次出现的右端点是什么。如果当前没出现过那 \(cov\) 就是 \(0\)。

• 加字符：加完字符后在 PAM 上往上跳，找到在 \([l,r]\) 内的最长回文后缀。这是唯一有可能成为新的回文子串的串，因此判一下 \(cov\) 即可更新答案。接下来我们要更新 \(cov\) 数组。考虑只在这个最长回文后缀处打标记，当这个最长回文后缀不再出现的时候再推标记给他父亲。
• 删字符：考虑拉出所有左端点至少是当前位置的节点，把他们删了并推标记。我们发现如果一个应当被删，那么他一定是叶子节点（即没有儿子出现过），因此该点的 \(cov_i\) 一定是准确的（即该推的标记都推了）。所以再记一下每个点有多少儿子出现了就行。

具体细节见代码。

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
using namespace std;
const int N = 1e6 + 7;
int ch[N][26], cov[N], f[N], len[N], p;
char s[N];
int getfa(int x) {
	for(; p < len[x] + 1 || s[p - len[x] - 1] != s[p]; x = f[x]) ;
	return x;
}
int lst, tot = 1; 
void ins() {
	lst = getfa(lst);
	if(!ch[lst][s[p] - 'a']) 
		++tot, f[tot] = ch[getfa(f[lst])][s[p] - 'a'], ch[lst][s[p] - 'a'] = tot, len[tot] = len[lst] + 2;
	lst = ch[lst][s[p] - 'a'];
}
char qs[10];
int n, m, curm = 1, ml = 1, xns, pos[N], cnt[N];
vi vc[N]; 
void cv(int x, int w) {
	if(x <= 1) return ;
	if(!cov[x]) xns += 1, cnt[f[x]] += 1;
	if(w > cov[x]) cov[x] = w, vc[w - len[x] + 1].emplace_back(x);
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> m, f[0] = 1, len[1] = -1;
	while(m--) {
		cin >> (qs + 1);
		if(qs[2] == 'u') {
			cin >> (qs + 1);
			n += 1, s[n] = qs[1], p = n, ins();
			for(; len[lst] > n - ml + 1; lst = f[lst]) ;
			cv(lst, n);
		} else {
			for(const int &u : vc[ml]) 
				if(!cnt[u] && len[u] == cov[u] - ml + 1) 
					--xns, cv(f[u], cov[u]), cov[u] = 0, cnt[f[u]] -= 1;
			++ml;	
		} 
		cout << xns << '\n';
	}
	return 0;
}