CF1738H Palindrome Addicts

你的任务是维护一个只包含小写英文字母的队列，具体操作如下： - “push $c$”：在队列的末尾插入一个字母 $c$； - “pop”：从队列的开头删除一个字母。 初始时，队列为空。 每次操作后，你需要统计由队列从头到尾拼接得到的字符串中，不同回文子串的数量。 特别地，空字符串的不同回文子串数量为 $0$。 一个长度为 $n$ 的字符串 $s[1..n]$ 是回文的，当且仅当对于每个 $1 \leq i \leq n$，都有 $s[i] = s[n-i+1]$。 字符串 $s[l..r]$ 是字符串 $s[1..n]$ 的一个子串，当且仅当 $1 \leq l \leq r \leq n$。 两个字符串 $s[1..n]$ 和 $t[1..m]$ 是不同的，当且仅当满足以下条件之一： - $n \neq m$； - 存在某个 $1 \leq i \leq \min\{n,m\}$，使得 $s[i] \neq t[i]$。

第一行是一个整数 $q$（$1 \leq q \leq 10^6$），表示操作的数量。 接下来的 $q$ 行，每行包含一个如下操作之一： - “push $c$”：在队列末尾插入一个小写英文字母 $c$； - “pop”：从队列开头删除一个字母。 保证在队列为空时不会进行“pop”操作。

每次操作后，输出当前队列表示的字符串中，不同回文子串的数量。

设 $s_k$ 表示第 $k$ 次操作后队列中的字符串，$c_k$ 表示 $s_k$ 的不同回文子串数量。下表展示了样例的详细信息。 | $k$ | $s_k$ | $c_k$ | |-----|------------|-------| | 1 | a | 1 | | 2 | 空 | 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 | 需要注意的是： - 第 $2$ 次操作后，字符串为空，因此没有子串，答案为 $0$； - 第 $8$ 次操作后，字符串为 “aabbaa”。其 $6$ 个不同的回文子串为 “a”， “aa”， “aabbaa”， “abba”， “b”， “bb”。 由 ChatGPT 4.1 翻译