http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1830
额 学弟发问 然后骚扰五姑娘 然后诞生此物。。。
思路
首先生成一个数组 用来存储每个数的前面距离它最近的相同数字的下标
然后利用线段数 查询区间最大值
最大值就是 答案的下标 然后输出
然后需要注意 下标如果在查询的范围外 就返回-1 (第一次我错在这里)
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
using namespace std;
struct node{
int max,l,r;
}tree[500010*3];
int n,q,num[500010],ans[500010],a,b;
int creat(int root,int left,int right){
tree[root].l=left;
tree[root].r=right;
if(left==right)return tree[root].max=ans[left];
int a,b,middle=(left+right)/2;
a=creat(2*root,left,middle);
b=creat(2*root+1,middle+1,right);
return tree[root].max=max(a,b);
}
int query(int root,int left,int right){
if(tree[root].l>right||tree[root].r<left)return -1;
if(left<=tree[root].l&&tree[root].r<=right){
if(tree[root].max>=a)return tree[root].max;
else return -1;
}
int aa,bb;
aa=query(2*root,left,right);
bb=query(2*root+1,left,right);
//printf("query root:%3d left:%3d right:%3d a:%3d b:%3d\n",root,left,right,a,b);
return max(aa,bb);
}
int main(){
int i,j,k;
map<int,int> mp;
map<int,int>::iterator it;
while(scanf("%d",&n)!=EOF){
mp.clear();
memset(ans,-1,sizeof(ans));
for(i=1;i<=n;i++){
scanf("%d",&num[i]);
it=mp.find(num[i]);
if(it==mp.end()){
mp[num[i]]=i;
}else {
ans[i]=(*it).second;
(*it).second=i;
}
}
creat(1,1,n);
scanf("%d",&q);
while(q--){
scanf("%d%d",&a,&b);
int qq=query(1,a,b);
if(qq<=0)puts("jiong");
else printf("%d\n",num[qq]);
}
puts("");
}
return 0;
}