ZOJ Monthly, August 2012 - A Alice's present MAP 함수

Alice's present
Time Limit: 5 Seconds     
Memory Limit: 65536 KB
As a doll master, Alice owns a wide range of dolls, and each of them has a number tip on it's back, the tip can be treated as a positive integer. (the number can be repeated). One day, Alice hears that her best friend Marisa's birthday is coming , so she decides to sent Marisa some dolls for present. Alice puts her dolls in a row and marks them from 1 ton. Each time Alice chooses an interval from i to j in the sequence ( includei and j ) , and then checks the number tips on dolls in the interval from right to left. If any number appears more than once , Alice will treat this interval as unsuitable. Otherwise, this interval will be treated as suitable.
This work is so boring and it will waste Alice a lot of time. So Alice asks you for help .

Input

There are multiple test cases. For each test case:
The first line contains an integer n ( 3≤ n ≤ 500,000) ,indicate the number of dolls which Alice owns.
The second line contains n positive integers , decribe the number tips on dolls. All of them are less than 2^31-1.The third line contains an intergerm ( 1 ≤ m ≤ 50,000 ),indicate how many intervals Alice will query. Then followed by m lines, each line contains two integeru, v ( 1≤ u< v≤ n ),indicate the left endpoint and right endpoint of the interval.Process to the end of input.

Output

For each test case:
For each query,If this interval is suitable , print one line "OK".Otherwise, print one line ,the integer which appears more than once first.
Print an blank line after each case.

Sample Input

5
1 2 3 1 2
3
1 4
1 5
3 5
6
1 2 3 3 2 1
4
1 4
2 5
3 6
4 6

Sample Output

1
2
OK

3
3
3
OK

Hint

Alice will check each interval from right to left, don't make mistakes.
제목:
n 개 수를 입력하고 m 개 질문 구간에서 오른쪽에서 왼쪽으로 중복된 숫자가 있는지 물어보세요. 출력이 있으면 첫 번째 중복된 숫자가 있으면 출력이 없으면 OK.
사고방식: 모든 구간에 접근하여 맵 함수의 일대일 성질을 이용하여 find 함수를 이용하여 존재하는지 여부를 보고 존재하지 않으면 이 수와 1을 맵에 추가합니다 ()
찾으면 이 수를 반복해서 출력하면 됩니다.

#include<stdio.h>
#include<map>
#include<cstring>
using namespace std;
int a[500500];
map<int,int>mp;
int main()
{
	int n,i,m,left,right;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		scanf("%d",&m);
		while(m--)
		{
			scanf("%d%d",&left,&right);
			mp.clear();
			for(i=right;i>=left;i--)
			{
				if(mp.find(a[i])==mp.end())
					mp[a[i]]=1;
				else
				{break;}
			}
			if(i==left-1)
				printf("OK
");
			else
				printf("%d
",a[i]);
		}
		printf("
");
	}
	return 0;
}