Election Quick Report

题目描述

有一场选举要从编号为 $1, 2, \ldots, N$ 的 $N$ 位候选人中选出一名获胜者，已经投出了 $M$ 票。 每张票恰好投给一位候选人，第 $i$ 张票投给候选人 $A_i$。 按从第一张到最后一张的顺序统计选票，并且在每次计票后更新并显示当前的获胜者。 在已统计的票中得票最多的候选人为获胜者。如果有多个候选人的票数并列最多，则编号最小的候选人为获胜者。 对于每个 $i = 1, 2, \ldots, M$，确定只统计前 $i$ 张票时的获胜者。

输入格式

输入由标准输入给出，格式如下： $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_M$

输出格式

输出 $M$ 行。 第 $i$ 行应当包含只统计前 $i$ 张票时的获胜者的候选人编号。

3 7
1 2 2 3 1 3 3

1
1
2
2
1
1
3

100 5
100 90 80 70 60

100
90
80
70
60

9 8
8 8 2 2 8 8 2 2

8
8
8
2
8
8
8
2

提示

$1 \leq N, M \leq 200000$ $1 \leq A_i \leq N$ 所有输入值均为整数。记 $C_i$ 为候选人 $i$ 的票数。

统计完第一张票后，$(C_1, C_2, C_3) = (1, 0, 0)$，所以获胜者是 $1$。 统计完第二张票后，$(C_1, C_2, C_3) = (1, 1, 0)$，所以获胜者是 $1$。 统计完第三张票后，$(C_1, C_2, C_3) = (1, 2, 0)$，所以获胜者是 $2$。 统计完第四张票后，$(C_1, C_2, C_3) = (1, 2, 1)$，所以获胜者是 $2$。 统计完第五张票后，$(C_1, C_2, C_3) = (2, 2, 1)$，所以获胜者是 $1$。 统计完第六张票后，$(C_1, C_2, C_3) = (2, 2, 2)$，所以获胜者是 $1$。 统计完第七张票后，$(C_1, C_2, C_3) = (2, 2, 3)$，所以获胜者是 $3$。

标签: AtCoder|abc329D

来源

AtCoder|abc329D