← 返回题目列表

Codeforces · 1738/H

H. 回文瘾君子

中文机器翻译题面 查看原题

你的任务是维护一个由小写英文字母组成的队列,如下所示:

- “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$$$”。