zoj 3633

L - Alice's present

Time Limit:5000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Submit Status

Description

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 to n. Each time Alice chooses an interval from i to jin the sequence ( include i 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 interger m ( 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.

噗。。

想了半天都没想明白。。。

一看市县5s。。要不就暴力来一发？

虽然1.6s通过的。。。但总觉得哪里不对。。

正解应该是线段树之类的吧？

sad

北京之前一定把基础线段树弄回了。。

至少。。。

抄几遍模板。。。

/*************************************************************************
    > File Name: zoj/3633.cpp
    > Author: 111qqz
    > Email: rkz2013@126.com 
    > Created Time: 2015年10月22日 星期四 18时26分27秒
************************************************************************/

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#include<cctype>
         
#define yn hez111qqz
#define j1 cute111qqz
#define ms(a,x) memset(a,x,sizeof(a))
using namespace std;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
typedef long long LL;
typedef double DB;
const int inf = 0x3f3f3f3f;
const int N=5E5+7;
int n,m;
int a[N],ans[N];
int l,r;
set<int>se;



int main()
{
  #ifndef  ONLINE_JUDGE 
   freopen("in.txt","r",stdin);
  #endif

   while (scanf("%d",&n)!=EOF)
   {
    

       for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);

       scanf("%d",&m);

       for ( int i = 0 ; i < m ; i++)
       {
       bool ok = true;
       scanf("%d %d",&l,&r);
       se.clear();

       for ( int j = r ; j >= l ; j--)
        {
//        cout<<"j:"<<j<<" a[j]:"<<a[j]<<endl;
        if (!se.count(a[j]))
        {
            se.insert(a[j]);
        }
        else
        {
            ok = false;
            printf("%d
",a[j]);
            break;
        }
        
        }
       if (ok) puts("OK");
       }
    puts("");

       
   }
  
   
 #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}