ZOJ Monthly, August 2012 - A : Alice's present

問題概要

長さN(<5e5)の数列Xが与えられる。以下のQ(<5e4)個のクエリを処理する。区間[l, r]を右から走査していったとき最初に2回出現する数を答える。どれも1回しか現れないなら指摘する。

解法

各iについて、自分より左側で最も近くに現れるindexを持っておく。後は区間内でRMQして最大のindexを取り出し、それが区間内に入っているか見れば良い。

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;
}