問題概要

長さ $N$ の数列 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。

各 $i = 1, 2, \dots, N$ について、 $A_{j} = A_{i}$ かつ $1 \le j \lt i$ を満たす最大の整数 $j$ を求めよ（存在しない場合は -1）。

制約

$1 \le N \le 2 \times 10^{5}$
$1 \le A_{i} \le 10^{9}$

考えたこと

基本的には次の情報を管理できる配列が欲しい。

last[v]：その時点で、 $A_{j} = v$ を満たす最大の $j$

ただし、 $1 \le A_{i} \le 10^{9}$ という制約を考えると、単純な配列だと $10^{9}$ ものサイズが必要になってしまう。このようなとき、連想配列が活躍する。連想配列は、配列の添字にさまざまな要素を入れられるようにしたものである。C++ では map 型が使える。

具体的には、map<int,int> 型の変数 last を用意しよう。全体として計算量は $O(N \log N)$ となる。

コード

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

int main() {
    int N, A;
    cin >> N;

    map<int, int> last;
    for (int i = 0; i < N; i++) {
        cin >> A;
        if (!last.count(A)) cout << -1 << " ";
        else cout << last[A] << " ";
        last[A] = i+1;
    }
    cout << endl;
}