Description
给出n个数，问你在区间[a,b]内从右到左第一个出现重复的数字是哪一个。
Input
每组样例第一行给出n，表示有n个数(3≤ n ≤ 500,000)。
第二行给出n个数，每个数不大于2^31。
然后给出一个Q，表示有Q次询问 (1 ≤ Q ≤ 50,000)。
接下来Q行每行两个数a，b (1 <= a < b <= n)。
Output
输出每次询问在[a,b]区间内第一次出现重复的数字是哪个，如果没有则输出”jiong”。
每一组样例后输出一个换行。
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
jiong
3
3
3
jiong
要从在区间L到R内找到第一个重复出现的的数，并且是从R遍历到L的过程中找到的第一个数，我们预处理出每一个数的上一次出现的位序，直接按值大小sort然后遍历找位序，再按位序sort回来，建立线段树，于是在线段树我们查询区间最大值，这个最大值即区间中第一次出现的重复的数的最近位置。检查这个值是否存在，若存在检查是否在区间内，符合条件直接输出即可
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct num
{
int i,num,next;
}a[500005];
struct node
{
int l,r,maxx;
}tree[500005*4];
bool cmp(num a,num b)
{
if(a.num==b.num)return a.i<b.i;
return a.num<b.num;
}
bool cmp2(num a,num b)
{
return a.i<b.i;
}
void build(int l,int r,int root)///建树
{
tree[root].l=l;
tree[root].r=r;
tree[root].maxx=-1;
if(l==r)
{
tree[root].maxx=a[l].next;
}
else
{
int mid=(l+r)/2;
build(l,mid,root*2);
build(mid+1,r,root*2+1);
tree[root].maxx=max(tree[root*2].maxx,tree[root*2+1].maxx);
}
}
int query(int l,int r,int root)
{
if(l<=tree[root].l&&tree[root].r<=r)
{
return tree[root].maxx;
}
else
{
int mid = (tree[root].l+tree[root].r)/2;
int res=-1;
if(l<=mid)
{
res = max(query(l,r,root*2),res);
}
if(r>=mid+1)
{
res = max(query(l,r,root*2+1),res);
}
return res;///返回最大值
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].num);
a[i].i=i;
}
sort(a+1,a+n+1,cmp);///按数的大小排序，得到相同数的位序，然后错位赋值前一个相同元素的位序
for(int i=n;i>=2;i--)
{
if(a[i].num==a[i-1].num) a[i].next=a[i-1].i;
else a[i].next=-1;
}
sort(a+1,a+1+n,cmp2);///将打乱顺序的数列按恢复成原序列(位序排序)
build(1,n,1);///将按顺序排列好并赋值了相同数下一位序的数组建立到线段树中
int q,l,r;
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&l,&r);///线段树最大值查询
int ans=query(l,r,1);
if(ans==-1||ans<l)printf("jiong
");
else printf("%d
",a[ans].num);
}
printf("
");
}
}