データ構造を用いたクエリ処理
G - ストリング・クエリ
O(N)
import sys import math import heapq import itertools from collections import deque from functools import reduce from string import ascii_lowercase # main def main(): Q = int(input()) que = deque() for q in range(Q): values = input().split() if values[0] == "1": c = values[1] x = int(values[2]) que.append([c, x]) else: d = int(values[1]) cnt = {} for c in ascii_lowercase: cnt[c] = 0 while d > 0 and len(que) > 0: c, x = que[0] if d >= x: d -= x cnt[c] += x que.popleft() else: cnt[c] += d que[0][1] -= d d = 0 ans = 0 for c in ascii_lowercase: ans += cnt[c] ** 2 print(ans) # エントリポイント if __name__ == '__main__': main()