ZOJ Monthly, August 2012 - A : Alice's present
問題概要
長さN(<5e5)の数列Xが与えられる。以下のQ(<5e4)個のクエリを処理する。区間[l, r]を右から走査していったとき最初に2回出現する数を答える。どれも1回しか現れないなら指摘する。
acceptされたコード
#include <cstdio> #include <vector> #include <algorithm> #include <map> using namespace std; typedef int rmq_t; const int INF = (int)(1.05e9); const int MAX_N = 500000; const int MAX_Q = 50000; int N, Q; int as[MAX_N]; int ls[MAX_N], rs[MAX_N]; bool init() { if (scanf("%d", &N) == EOF) { return false; } for (int i = 0; i < N; ++i) { scanf("%d", as + i); } scanf("%d", &Q); for (int i = 0; i < Q; ++i) { scanf("%d%d", ls+i, rs+i); --ls[i]; } return true; } void solve() { static StaticRangeMinimumQuery rmq; //最大値 rmq.resize(N); map<int,int> lastAppear; for (int i = 0; i < N; ++i) { if (lastAppear.find(as[i]) == lastAppear.end()) { rmq[i] = -INF; } else { rmq[i] = lastAppear[as[i]]; } lastAppear[as[i]] = i; } rmq.build(); for (int i = 0; i < Q; ++i) { int val = rmq.getValue(ls[i], rs[i]); if (val >= 0 && ls[i] <= val) { printf("%d\n", as[val]); } else { puts("OK"); } } puts(""); } int main() { for (;init();) { solve(); } return 0; }