您當(dāng)前位置：首頁 > 互聯(lián)網(wǎng) > ZOJ 3633 Alice's present(線段樹）

ZOJ 3633 Alice's present(線段樹）

來源：程序員人生發(fā)布時(shí)間：2014-11-09 10:02:51 閱讀次數(shù)：2809次

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 j in 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⑴. 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 integer u, 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.

題意：給定1個(gè)區(qū)間，詢問區(qū)間有木有重復(fù)的數(shù)。

map1下，表示某個(gè)數(shù)的靠左側(cè)相同的位置，沒有置為⑴；轉(zhuǎn)化為詢問區(qū)間最大值。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> typedef long long LL; using namespace std; #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define CLEAR( a , x ) memset ( a , x , sizeof a ) const int maxn=500000+100; int t[maxn<<2],a[maxn],b[maxn]; map<int,int>f; //int hash[maxn]; int n,m; void pushup(int rs) { t[rs]=max(t[rs<<1],t[rs<<1|1]); } void build(int rs,int l,int r) { if(l==r) { t[rs]=a[l]; return ; } int mid=(l+r)>>1; build(rs<<1,l,mid); build(rs<<1|1,mid+1,r); pushup(rs); } int query(int rs,int l,int r,int x,int y) { if(x<=l&&y>=r) return t[rs]; int mid=(l+r)>>1; int res1,res2; res1=res2=⑴; if(x<=mid) res1=query(rs<<1,l,mid,x,y); if(y>mid) res2=query(rs<<1|1,mid+1,r,x,y); return max(res1,res2); } int main() { int x,y; while(~scanf("%d",&n)) { f.clear(); // CLEAR(hash,0); REPF(i,1,n) { scanf("%d",&x); b[i]=x; if(!f[x]) { f[x]=i; a[i]=⑴; } else { a[i]=f[x]; f[x]=i; } } build(1,1,n); scanf("%d",&m); REP(i,m) { scanf("%d%d",&x,&y); int ans=query(1,1,n,x,y); if(ans<x) puts("OK"); else printf("%d ",b[ans]); } puts(""); } return 0; }

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
程序員人生