你的任务是维护一个由小写英文字母组成的队列,如下所示:
- “push $$$c$$$”:在队列末尾插入字母$$$c$$$;
- “pop”:从队列前面删除一封信。
最初,队列是空的。
每次操作后,系统都会要求您计算字符串中不同回文子串的数量,这些回文子串是通过将队列从前到后的字母连接起来而获得的。
特别是,空字符串的不同回文子串的数量为$$$0$$$。
如果对于每个 $$$1 \leq i \leq n$$$,$$$s[i] = s[n-i+1]$$$,则长度为 $$$n$$$ 的字符串 $$$s[1..n]$$$ 是回文。
字符串 $$$s[l..r]$$$ 是字符串 $$$s[1..n]$$$ 对于每个 $$$1 \leq l \leq r \leq n$$$ 的子字符串。
如果以下至少一项成立,则两个字符串 $$$s[1..n]$$$ 和 $$$t[1..m]$$$ 是不同的。
- $$$n \neq m$$$;
- $$$s[i] \neq t[i]$$$ 对于某些 $$$1 \leq i \leq \min\{n,m\}$$$。
输入
第一行是一个整数$$$q$$$ ($$$1 \leq q \leq 10^6$$$),表示操作次数。
然后是 $$$q$$$ 行。以下每一行都包含如下操作之一。
- “push $$$c$$$”:在队列后面插入字母$$$c$$$,其中$$$c$$$为小写英文字母;
- “pop”:从队列前面删除一封信。
保证队列为空时不会执行“pop”操作。
输出
每次操作后,打印队列中呈现的字符串中不同回文子字符串的数量。
示例
输入 #1
12 push a pop push a push a push b push b push a push a pop pop pop push b
输出 #1
1 0 1 2 3 4 5 6 5 4 3 4
注意
令 $$$s_k$$$ 为第 $$$k$$$ 操作后队列中出现的字符串,并令 $$$c_k$$$ 为 $$$s_k$$$ 的不同回文子串的数量。下表显示了该示例的详细信息。
$$$k$$$$$$s_k$$$$$$c_k$$$$$$1$$$$$$a$$$$$$1$$$$$$2$$$$$$\textsf{空}$$$$$$0$$$ $$$3$$$$$$a$$$$$$1$$$$$$4$$$$$$aa$$$$$$2$$$$$$5$$$$$$aab$$$$$$3$$$$$$6$$$$$$aabb $$$$$$4$$$$$$7$$$$$$阿巴$$$$$$5$$$$$$8$$$$$$阿巴a$$$$$$6$$$$$$9$$$$$$阿巴a$$$$ $$5$$$$$$10$$$$$$bbaa$$$$$$4$$$$$$11$$$$$$baa$$$$$$3$$$$$$12$$$$$$baab$$$$$$4$$$
值得指出的是
- 在 $$$2$$$-nd 操作之后,字符串为空,因此没有子字符串。所以答案是$$$0$$$;
- 第 $$$8$$$ 操作后,字符串为“$$$aabbaa$$$”。 $$$6$$$ 不同的回文子串是“$$$a$$$”、“$$$aa$$$”、“$$$aabbaa$$$”、“$$$abba$$$”、“$$$b$$$”和“$$$bb$$$”。