Palindrome Addicts
Contest: Codeforces Global Round 22
Difficulty rating: 3300
Tags: data structures, strings

Your task is to maintain a queue consisting of lowercase English letters as follows:

- "push $$$c$$$": insert a letter $$$c$$$ at the back of the queue;
- "pop": delete a letter from the front of the queue.

Initially, the queue is empty.

After each operation, you are asked to count the number of distinct palindromic substrings in the string that are obtained by concatenating the letters from the front to the back of the queue.

Especially, the number of distinct palindromic substrings of the empty string is $$$0$$$.

A string $$$s[1..n]$$$ of length $$$n$$$ is palindromic if $$$s[i] = s[n-i+1]$$$ for every $$$1 \leq i \leq n$$$.

The string $$$s[l..r]$$$ is a substring of string $$$s[1..n]$$$ for every $$$1 \leq l \leq r \leq n$$$.

Two strings $$$s[1..n]$$$ and $$$t[1..m]$$$ are distinct, if at least one of the following holds.

- $$$n \neq m$$$;
- $$$s[i] \neq t[i]$$$ for some $$$1 \leq i \leq \min\{n,m\}$$$.

Input format:
The first line is an integer $$$q$$$ ($$$1 \leq q \leq 10^6$$$), indicating the number of operations.

Then $$$q$$$ lines follow. Each of the following lines contains one of the operations as follows.

- "push $$$c$$$": insert a letter $$$c$$$ at the back of the queue, where $$$c$$$ is a lowercase English letter;
- "pop": delete a letter from the front of the queue.

It is guaranteed that no "pop" operation will be performed when the queue is empty.

Output format:
After each operation, print the number of distinct palindromic substrings in the string presented in the queue.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
Let $$$s_k$$$ be the string presented in the queue after the $$$k$$$-th operation, and let $$$c_k$$$ be the number of distinct palindromic substrings of $$$s_k$$$. The following table shows the details of the example.

$$$k$$$$$$s_k$$$$$$c_k$$$$$$1$$$$$$a$$$$$$1$$$$$$2$$$$$$\textsf{empty}$$$$$$0$$$$$$3$$$$$$a$$$$$$1$$$$$$4$$$$$$aa$$$$$$2$$$$$$5$$$$$$aab$$$$$$3$$$$$$6$$$$$$aabb$$$$$$4$$$$$$7$$$$$$aabba$$$$$$5$$$$$$8$$$$$$aabbaa$$$$$$6$$$$$$9$$$$$$abbaa$$$$$$5$$$$$$10$$$$$$bbaa$$$$$$4$$$$$$11$$$$$$baa$$$$$$3$$$$$$12$$$$$$baab$$$$$$4$$$

It is worth pointing out that

- After the $$$2$$$-nd operation, the string is empty and thus has no substrings. So the answer is $$$0$$$;
- After the $$$8$$$-th operation, the string is "$$$aabbaa$$$". The $$$6$$$ distinct palindromic substrings are "$$$a$$$", "$$$aa$$$", "$$$aabbaa$$$", "$$$abba$$$", "$$$b$$$", and "$$$bb$$$".

Example input:
12
push a
pop
push a
push a
push b
push b
push a
push a
pop
pop
pop
push b

Example output:
1
0
1
2
3
4
5
6
5
4
3
4

Editorial:
To count the number of distinct palindromic substrings, we adopt the powerful data structure called eertree (also known as palindromic tree or palindromic automaton). The number of distinct palindromic substrings of a string $$$s$$$ is related to the number of nodes in the eertree of $$$s$$$. See Wikipedia for its standard operations. In the following, we will consider how to maintain the eertree under push and pop queue operations.
It is a standard trick to push a character at the back. So we only need to consider how to pop a character at the front. The key issue is to delete some nodes when they no longer exist. To achieve this, we maintain the following information of each node $$$v$$$:
• $$$\texttt{link_cnt}$$$: the number of nodes that link to $$$v$$$.
• $$$\texttt{rightmost_occurrence}$$$: the rightmost occurrence of $$$v$$$.
• $$$\texttt{second_rightmost_occurrence}$$$: the second rightmost occurrence of $$$v$$$.
Now it remains to consider how to maintain $$$\texttt{rightmost_occurrence}$$$ and $$$\texttt{second_rightmost_occurrence}$$$ in a lazy manner.
• After a character $$$c$$$ has been pushed at the back of the string $$$s$$$, let $$$v$$$ be the longest palindromic suffix of the current string $$$sc$$$. Update $$$\texttt{rightmost_occurrence}[v]$$$ and $$$\texttt{second_rightmost_occurrence}[v]$$$ immediately with the new occurrence of $$$v$$$.
• When a character is being popped from the front of the string $$$s$$$, let $$$v$$$ be the longest palindromic prefix of the current string (right before the pop operation). If $$$v$$$ is unique in $$$s$$$, then let $$$u$$$ be the node that $$$v$$$ links to, and update $$$\texttt{rightmost_occurrence}[u]$$$ and $$$\texttt{second_rightmost_occurrence}[u]$$$ with the occurrence of $$$u$$$ induced by $$$v$$$ (which is a suffix of $$$v$$$). Here, note that $$$u$$$ occurs at least twice in $$$v$$$ as its prefix and suffix; and the suffix $$$u$$$ of $$$v$$$ is desired as induced by $$$v$$$.
In this way, we can maintain the eertree under push and pop queue operations in $$$O(\Sigma n)$$$ time, where $$$\Sigma = 26$$$ is the size of alphabet.
Further reading: Takuya Mieno, Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Palindromic trees for a sliding window and its applications. Information Processing Letters, 173:106174, 2022.
An alternative approach
Answer the queries offline.
Since we only push characters at the back and remove characters at the front, we can deal with all operations offline and find the whole string $$$s$$$ with its characters deleted during the operations (This can be achieved easily by only considering push operations). For example, the whole string of the sample input is "$$$aaabbaab$$$".
In this way, every query of the number of distinct palindromic substrings is a range query of the form $$$(l, r)$$$ that asks the number of distinct palindromic substrings in $$$s[l..r]$$$. Indeed, this kind of queries can be answered in $$$O(\log n)$$$ time per query with $$$O(n \log n)$$$ time preprocess.
Further reading: Mikhail Rubinchik and Arseny M. Shur. Counting palindromes in substrings. In Proceedings of the 24th International Conference on String Processing and Information Retrieval, pages 290–303, 2017.