ABC391 - C - Pigeonhole Query

問題

以下の配列・変数を持っておくことで高速に各クエリを処理できる。

$ \mathrm{pigeons}_i:=ハト$ iがどこの巣にいるか？を記録する配列

$ \mathrm{nests}_j:=巣$ jに何羽のハトがいるか？を記録する配列

$ C:=複数のハトがいる巣はいくつあるか？を記録する変数

クエリ$ 1$ (p,h)

ハト$ pがいる巣を$ \mathrm{pigeons}から取得し、その巣のハトの数（$ \mathrm{nests}）をデクリメントする。

このとき巣にいるハトの数が複数でなくなった場合（つまり$ 1になった場合）、$ Cをデクリメントする。

次の巣$ hのハトの数をインクリメントする。ハトがいる巣も更新する。

このとき巣にいるハトの数が複数になった場合（つまり$ 2になった場合）、$ Cをインクリメントする。

クエリ$ 2

$ Cを出力

code: c.py

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

nests = 1 * N

C = 0

ans = []

for _ in range(Q):

query = list(map(int, input().split()))

q = query0

if q == 1:

_, p, h = query

p -= 1

h -= 1

nests[pigeonsp] -= 1

if nests[pigeonsp] == 1:

C -= 1

nestsh += 1

if nestsh == 2:

C += 1

pigeonsp = h

else:

ans.append(C)

print(*ans, sep="\n")