読者です 読者をやめる 読者になる 読者になる

Live Archive 5881 - Unique Encryption Keys

問題

意訳
数列A(A[1]...A[N])が与えられる。
Q個のクエリに答えよ。
クエリは2つの整数B, E(B<=E)が与えられる。
A[B~E]の中で複数出現するものをどれか一つ答えよ。

Live Archiveではおそらくスペシャルジャッジになっていないので、AC取るにはA[B~E]を順に見たときに初めてに繰り返し現れる値A[i]を求めよ。
その値が存在しないならそれを指摘せよ。

解法

前処理として、
Aを後ろから舐める。
A[i]を見るとき、A[i]と同じ値が最後にでた位置をpre[A[i]]として、
ans[i] = min(ans[i+1], pre[A[i]])とする。
pre[A[i]] := i と更新する。
ans[A[i]]にはA[i]から順に見た時に初めて繰り返し現れる位置が入る。

各クエリについてans[B]の位置にある値を出力すれば良い。