AT_past202004_g ストリング・クエリ

对字符串 $S$ 进行 $Q$ 次操作。初始时，字符串 $S$ 为空字符串。 第 $i$ 次操作的类型由整数 $T_i\ (1\leq i\leq Q)$ 表示，具体内容如下： - 当 $T_i=1$ 时： - 给定一个小写英文字母 $C_i$ 和一个整数 $X_i$。在 $S$ 的末尾添加 $X_i$ 个 $C_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$ > $\vdots$ > $Query_Q$ 第 $2$ 行到第 $Q+1$ 行的 $Query_i$ 有以下两种形式之一： > $1\ C_i\ X_i$ 表示执行 $T_i=1$ 的操作。 > $2\ D_i$ 表示执行 $T_i=2$ 的操作。

对于每个 $T_i=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 初始 $S$ 为空字符串。 - 第 1 次操作后，$S$ 变为 `aaaaa`。 - 第 2 次操作后，$S$ 变为 `aa`。删除了 $3$ 个 `a`，其他字符未被删除。 - 第 3 次操作后，$S$ 变为 `aatttttttt`。 - 第 4 次操作后，$S$ 变为 `aattttttttcccccccccc`。 - 第 5 次操作前，$S$ 长度为 $20$，操作后 $S$ 变为空字符串。删除了 $2$ 个 `a`，$10$ 个 `c`，$8$ 个 `t`。 - 第 6 次操作后，$S$ 仍为空字符串，没有字符被删除。 因此，第 2 次操作输出 $3^2+0^2+\cdots+0^2=9$，第 5 次操作输出 $2^2+10^2+8^2=168$，第 6 次操作输出 $0$。 ### 样例解释 2 初始 $S$ 为空字符串。 - 第 1 次操作后，$S$ 变为 `xxxxx`。 - 第 2 次操作后，$S$ 变为 `xxxxxyyyyyyyy`。 - 第 3 次操作后，$S$ 变为 `yyyyyy`。删除了 $5$ 个 `x`，$2$ 个 `y`，$5^2+2^2=29$。 - 第 4 次操作后，$S$ 变为 `yyyyyyzzzzzzzz`。 由 ChatGPT 4.1 翻译