← 返回题目列表

AtCoder · past202004_g

G. 字符串查询

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

分数: 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.

约束

  • 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