G - ストリング・クエリ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

文字列 S に対して Q 回の操作を行います。初め文字列 S は空文字列です。

i 回目の操作の種類は整数 T_i (1 \leq i \leq Q) で表され、その内容は以下の通りです。

  • T_i = 1 のとき
    • 英小文字 C_i と整数 X_i が与えられる。S の末尾に C_i を X_i 文字追加する。
  • T_i = 2 のとき
    • 整数 D_i が与えられる。S の先頭から D_i 文字を削除する。S の長さが D_i 文字以下である場合は、S は空文字列となる。 そして、この操作でa, b, c, \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 または 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 の操作が 1 つ以上存在する

入力

入力は以下の形式で標準入力から与えられる。

Q
Query_1
:
Query_Q

2 行目から Q+1 行目の Query_i は以下の 2 つのいずれかである。

1 C_i X_i

T_i = 1 として操作を行うことを表す。

2 D_i

T_i = 2 として操作を行うことを表す。

出力

T_i = 2 である操作それぞれに対して順番に、各文字種の削除された文字数の 2 乗の和を出力せよ。

入力例 1

6
1 a 5
2 3
1 t 8
1 c 10
2 21
2 4

出力例 1

9
168
0

初め S は空文字列です。

  • 1 回目の操作の後、S は aaaaa となります。
  • 2 回目の操作の後、S は aa となります。a が 3 文字削除され、他の文字は削除されていません。
  • 3 回目の操作の後、S は aatttttttt となります。
  • 4 回目の操作の後、S は aattttttttcccccccccc となります。
  • 5 回目の操作の後、操作前の S の長さは 20 であるので、S は空文字列となります。 a が 2 文字、c が 10 文字、t が 8 文字削除されています。
  • 6 回目の操作の後、S は空文字列のままです。どの文字も削除されていません。

よって、2 回目の操作では 3^2 + 0^2 + \cdots + 0^2 = 9 を、5 回目の操作では 2^2 + 10^2 + 8^2 = 168 を出力してください。 6 回目の操作ではどの文字も削除されていないので、0 を出力してください。

入力例 2

4
1 x 5
1 y 8
2 7
1 z 8

出力例 2

29

初め S は空文字列です。

  • 1 回目の操作の後、S は xxxxx となります。
  • 2 回目の操作の後、S は xxxxxyyyyyyyy となります。
  • 3 回目の操作の後、S は yyyyyy となります。x が 5 文字、y が 2 文字削除されています。5^2 + 2^2 = 29 です。
  • 4 回目の操作の後、S は yyyyyyzzzzzzzz となります。

入力例 3

3
1 p 3
1 q 100000
2 100000

出力例 3

9999400018

Score : 6 points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Let us perform Q operations on a string S, which is initially empty.

The type of the i-th operation is represented by an integer T_i (1 \leq i \leq Q), as follows:

  • If T_i = 1:
    • Given a lowercase English letter C_i and an integer X_i, append X_i copies of C_i to the end of S.
  • If T_i = 2:
    • Given an integer D_i, erase the first D_i characters in S. If the length of S is D_i or less, S becomes empty. Then, find the number of as deleted in this operation, bs deleted in this operation, \cdots, and zs deleted in this operation. Let del_a, del_b, \cdots, del_z be the numbers of characters deleted. We ask you to print the value {del_a}^2 + {del_b}^2 + \cdots + {del_z}^2.

Constraints

  • 1 \leq Q \leq 10^5
  • T_i = 1 or 2.
  • C_i is a lowercase English letters.
  • 1 \leq X_i \leq 10^5
  • 1 \leq D_i \leq 10^5
  • Q, T_i, X_i, and D_i are integers.
  • There is at least one operation with T_i = 2.

Input

Input is given from Standard Input in the following format:

Q
Query_1
:
Query_Q

Here, on the 2-nd through the (Q+1)-th lines, Query_i is one of the following:

1 C_i X_i

representing an operation with T_i = 1, and:

2 D_i

representing an operation with T_i = 2.

Output

For each operation with T_i = 2 in order, print the value {del_a}^2 + {del_b}^2 + \cdots + {del_z}^2 described in Problem Statement.

Sample Input 1

6
1 a 5
2 3
1 t 8
1 c 10
2 21
2 4

Sample Output 1

9
168
0

Initially, S is empty.

  • After the 1-st operation, S is aaaaa.
  • After the 2-nd operation, S is aa. Here, just three as get deleted.
  • After the 3-rd operation, S is aatttttttt.
  • After the 4-th operation, S is aattttttttcccccccccc.
  • After the 5-th operation, S is empty, since the length of S is 20 before this operation. Here, two as, ten cs, and eight ts get deleted.
  • After the 6-th operation, S is still empty. No characters get deleted.

Therefore, for the second operation, print 3^2 + 0^2 + \cdots + 0^2 = 9; for the fifth operation, print 2^2 + 10^2 + 8^2 = 168; for the sixth operation where no characters get deleted, print 0.

Sample Input 2

4
1 x 5
1 y 8
2 7
1 z 8

Sample Output 2

29

Initially, S is empty.

  • After the 1-st operation, S is xxxxx.
  • After the 2-nd operation, S is xxxxxyyyyyyyy.
  • After the 3-rd operation, S is yyyyyy. Here, five xs and two ys get deleted, and 5^2 + 2^2 = 29.
  • After the 4-th operation, S is yyyyyyzzzzzzzz.

Sample Input 3

3
1 p 3
1 q 100000
2 100000

Sample Output 3

9999400018