AT_past202004_g ストリング・クエリ

[problemUrl]: https://atcoder.jp/contests/past202004-open/tasks/past202004_g 文字列 $ 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 $ を出力する。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 乗の和を出力せよ。

### 注意 この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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 $ つ以上存在する ### Sample Explanation 1 初め $ 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 $ を出力してください。 ### Sample Explanation 2 初め $ S $ は空文字列です。 - $ 1 $ 回目の操作の後、$ S $ は `xxxxx` となります。 - $ 2 $ 回目の操作の後、$ S $ は `xxxxxyyyyyyyy` となります。 - $ 3 $ 回目の操作の後、$ S $ は `yyyyyy` となります。`x` が $ 5 $ 文字、`y` が $ 2 $ 文字削除されています。$ 5^2\ +\ 2^2\ =\ 29 $ です。 - $ 4 $ 回目の操作の後、$ S $ は `yyyyyyzzzzzzzz` となります。