問題

$1, 2, \cdots, n$ の番号の付いた $n$ 人の候補者から当選者を1人選ぶ選挙があり、全体で $m$ 票の投票があった。

この選挙において、 $i$ 番目の投票先は ${a}_{i}$ である。

1票ごとに順に開票を行うとき、1票ごとに開票した時点での当選者を表示せよ。

ただし、開票された時点で最も得票数を得ている候補者が当選となり、複数人いる場合は、そのうち番号が最も小さい者が当選者となる。

入力

1行目には整数 $n, m$ が与えられる。

その次の行には投票先を表す $m$ 個の整数 ${a}_{i}$ が1行に渡って与えられる。

条件

$1 \leq n, m \leq 2 \times {10}^{5}$
$1 \leq {a}_{i} \leq n$
入力される数値はすべて整数である。

出力

$m$ 行に渡り、 $i$ 番目の票の開票が終わった時点での当選者の番号を表示すること。

解法

「 $i$ 回目の開票が終わるたびに、 $n$ 人分の得票数を確認してソートする」という方法でも開票のたびに当選者の表示こそできますが、毎回ソートを行うことから、これは $O( (mn) \log (n) )$ だけの計算量がかかってしまいます。

$1 \leq n, m \leq 2 \times {10}^{5}$ であることから、 $n, m$ が最大値をとるときなどでは、この方法では実行時間制限を超過してしまいます。

ここで、開票が行われた際に、新たに票を得るのは1人のみです。この人以外は得票数に変動はないため、開票直後での当選者となれる可能性があるのは、「開票直前まで当選者であった人」か「新たに票を得た人」のいずれかのみとなります。

従って、開票直前での「当選者」と「その得票数」の情報を保持しておけば、開票を行うたびにその情報を更新することで、開票のたびに当選者を表示することができます。

この表示については $O(1)$ で行うことができ、 $m$ 回行うことから全体でも $O(m)$ の計算量で表示を行え、実行時間制限についても十分に間に合います。

ソースコード

int n, m, a[int(2e5 + 5)];
int cnt[int(2e5 + 5)]; // 各候補者の得票数を保持する配列 cnt
Pii ans = {0, 0}; // (得票数, 当選者) を記録する pair<int, int>

int main() {
  // 値の入力
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> a[i];
  }

  for (int i = 1; i <= m; i++) {
    cnt[a[i]]++; // i 番目の投票での得票者の cnt を 1 増やす

    if (ans.first < cnt[a[i]]) {
      ans = {cnt[a[i]], a[i]}; // もし、現在の当選者の得票数よりも a[i] の得票数が多いならば、 ans の値を更新する
    } else if (ans.first == cnt[a[i]]) {
      ans = {ans.first, min(ans.second, a[i])}; // もし、現在の当選者の得票数と同じならば、当選者の候補者番号を比較して ans の値を更新する
    }

    cout << ans.second << endl; // 当選者を表示する
  }

  return 0;
}