分数: 6 点
警告
2020 年 5 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。
考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。
问题陈述
让我们表演一下 Q 对字符串的操作 S,最初是空的。
的类型 i- 第一个操作由一个整数表示 T_i (1 \leq i \leq Q),如下:
- If T_i = 1:
- 给定一个小写英文字母 C_i 和一个整数 X_i,追加 X_i 副本 C_i 到年底 S.
- If T_i = 2:
- 给定一个整数 D_i,删除第一个 D_i 中的字符 S。如果长度为 S is D_i 或更少, S 变为空。
然后,找出数量
a在此操作中被删除,b在此操作中被删除, \cdots,和z在此操作中被删除。让 del_a, del_b, \cdots, del_z 是删除的字符数。我们要求您打印该值 {del_a}^2 + {del_b}^2 + \cdots + {del_z}^2.
- 给定一个整数 D_i,删除第一个 D_i 中的字符 S。如果长度为 S is D_i 或更少, S 变为空。
然后,找出数量
约束
- 1 \leq Q \leq 10^5
- T_i = 1 or 2.
- C_i 是小写英文字母。
- 1 \leq X_i \leq 10^5
- 1 \leq D_i \leq 10^5
- Q, T_i, X_i, 和 D_i 是整数。
- 至少有一项操作 T_i = 2.
输入
输入由标准输入按以下格式给出:
Q Query_1 : Query_Q
在这里,在 2-nd 通过 (Q+1)第行, Query_i 是以下之一:
1 C_i X_i
代表一个操作 T_i = 1,以及:
2 D_i
代表一个操作 T_i = 2.
输出
对于每个操作 T_i = 2 按顺序打印该值 {del_a}^2 + {del_b}^2 + \cdots + {del_z}^2 在问题陈述中描述。
示例输入 1
6 1 a 5 2 3 1 t 8 1 c 10 2 21 2 4
示例输出 1
9 168 0
最初, S 为空。
- 之后 1-st 操作, S is
aaaaa. - 之后 2-nd操作, S is
aa。这里,只有三个a被删除。 - 之后 3-rd操作, S is
aatttttttt. - 之后 4第次操作, S is
aattttttttcccccccccc. - 之后 5第次操作, S 为空,因为长度 S is 20 在此操作之前。在这里,两个
a秒,十cs,八t被删除。 - 之后 6第次操作, S 仍然是空的。没有字符被删除。
因此,对于第二个操作,打印 3^2 + 0^2 + \cdots + 0^2 = 9;对于第五次操作,打印 2^2 + 10^2 + 8^2 = 168;对于没有删除字符的第六次操作,打印 0.
示例输入 2
4 1 x 5 1 y 8 2 7 1 z 8
示例输出 2
29
最初, S 为空。
- 之后 1-st 操作, S is
xxxxx. - 之后 2-nd操作, S is
xxxxxyyyyyyyy. - 之后 3-rd操作, S is
yyyyyy。在这里,五个xs 和两个y被删除,并且 5^2 + 2^2 = 29. - 之后 4第次操作, S is
yyyyyyzzzzzzzz.
示例输入 3
3 1 p 3 1 q 100000 2 100000
示例输出 3
9999400018