zoj 3633 Alice's present

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4801

离线做，将查询区间从小到大排序，具体处理见代码

My Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define maxn 50002
 6 struct op 
 7 {
 8     int l,r,id;
 9 }mes[maxn];
10 int num[maxn*10],pos[maxn*10];
11 int sorted[maxn*10];
12 int ans[maxn];
13 int deal(int n)
14 {
15     int k=2;
16     for(int i=2;i<=n;i++)
17     if(sorted[i]!=sorted[i-1])
18     sorted[k++]=sorted[i];
19     return k-1;
20 }
21 bool cmp(struct op a,struct op b)
22 {
23     return a.r<b.r;
24 }
25 int binsearch(int l,int r,int key)
26 {
27     int m=(l+r)>>1;
28     if(sorted[m]==key)
29     return m;
30     if(key<sorted[m])
31     return binsearch(l,m-1,key);
32     return binsearch(m+1,r,key);
33 }
34 int main()
35 {
36     int n;
37     while(~scanf("%d",&n)){
38         memset(ans,-1,sizeof(ans));
39         memset(pos,-1,sizeof(pos));
40         for(int i=1;i<=n;i++){
41             scanf("%d",num+i);
42             sorted[i]=num[i];
43         }
44         sort(sorted+1,sorted+n+1);
45         int k=deal(n),j=1,l=-1,r=-1;
46         int m;
47         scanf("%d",&m);
48         for(int i=0;i<m;i++){
49             scanf("%d%d",&mes[i].l,&mes[i].r);
50             mes[i].id=i;
51         }
52         sort(mes,mes+m,cmp);
53         for(int i=0;i<m;i++){
54             while(j<=mes[i].r){
55                 int posj=binsearch(1,k,num[j]);
56                     if(pos[posj]>l){
57                         l=pos[posj];
58                         r=j;
59                     }
60                         pos[posj]=j;
61                         j++;
62                 }
63                 if(l>=mes[i].l)
64                 ans[mes[i].id]=num[r];
65             }
66         for(int i=0;i<m;i++){
67             if(ans[i]==-1)
68             printf("OK\n");
69             else
70             printf("%d\n",ans[i]);
71         }
72         printf("\n");
73     }
74     return 0;
75 }

看了一下题解，貌似可以用线段树在线查询，想了很久都没想到，就直接按自己的来做了。