E - Set Add Query https://atcoder.jp/contests/abc347/tasks/abc347_e

abc347_e.py

N, Q = map(int, input().split())
x = list(map(int, input().split()))

# (1) 各クエリ終了時点の|S|の累積和を作成
s = set()
s_size_acc = [0]
for i in range(Q):
    curr_x = x[i]
    if curr_x in s:
        s.remove(curr_x)
    else:
        s.add(curr_x)
    s_size_acc.append(s_size_acc[-1] + len(s))

# (2) 各要素が集合にいた期間でスコアを集計
s = set()
ans = [0] * (N + 1)
entry = [0] * (N + 1)
for i in range(Q):
    curr_x = x[i]
    if curr_x in s:
        ans[curr_x] += s_size_acc[i] - s_size_acc[entry[curr_x] - 1]
        entry[curr_x] = 0
        s.remove(curr_x)
    else:
        entry[curr_x] = i + 1
        s.add(curr_x)

# (3) 全クエリ終了時点で集合に残っている要素のスコアを集計
for i in range(1, N + 1):
    if entry[i] != 0:
        ans[i] += s_size_acc[Q] - s_size_acc[entry[i] - 1]

print(*ans[1:])