問題概要

$1$ 以上 $N$ 以下の整数からなる長さ $M$ の数列 $A_{1}, A_{2}, \dots, A_{M}$ が与えられる。

各 $i = 1, 2, \dots, M$ に対して、 $A_{1}, A_{2}, \dots, A_{i}$ の中で最も多く登場する値を答えよ。複数個ある場合はそのうちの最小の値を答えよ。

制約

$1 \le N, M \le 2 \times 10^{5}$

考えたこと

この問題のように、各 $i$ に対して $A_{1}, A_{2}, \dots, A_{i}$ に関するなんらかの値を求める問題では、次のことを考えるのが定石である。こういう考え方を差分更新などと呼んだりする。

$A_{1}, A_{2}, \dots, A_{i-1}$ に関する情報に対して、 $A_{i}$ を追加したときに情報がどのように変化するか (差分) を考える

今回は次の情報を差分更新していくことにしよう。

vector<int> num(N, 0) // 人 i の得票数
int max_num = 0 // 得票数の最大値
int max_person = -1 // 得票数が最大のメンバー (タイの場合は最小の番号)

各 $i$ に対して、 $A_{i}$ を追加したときの情報の更新は $O(1)$ の計算量で実現できる。具体的には、次のコードのように書ける。全体の計算量は $O(N + M)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    for (int i = 0; i < M; ++i) {
        cin >> A[i];
        --A[i];  // 0-indexed にしておく
    }
    
    // 差分更新していくデータ
    vector<int> num(N, 0);  // 人 i の得票数
    int max_num = 0;  // 得票数の最大値
    int max_person = -1;  // 得票数が最大のメンバー (タイの場合は最小の番号)
    
    // 順次データを更新していく
    for (int i = 0; i < M; ++i) {
        // 人 A[i] の得票数を増やす
        ++num[A[i]];
        
        if (num[A[i]] > max_num) {
            // それが最大値を更新する場合
            max_num = num[A[i]];
            max_person = A[i];
        } else if (num[A[i]] == max_num) {
            // 最大値がタイになる場合は最小番号をとる
            max_person = min(max_person, A[i]);
        }
        
        // 出力
        cout << max_person+1 << endl;
    }
}