题目链接:http://codeforces.com/contest/522/problem/D
题目大意: 给你一个长度为n的序列,然后有m次查询,每次查询输入一个区间[li,lj],对于每一个查询,输出在这个区间内的两个相等的数的最短距离,如果没有相等的则输出-1.
线段树+扫描线,线段树维护的值是区间的最小值,从后往前扫,然后每次要做的事有两个:
1.判断当前这个位置 i 的数刚刚是不是出现过,假设刚刚出现的位置是 l ,如果出现过,则在线段树中把l这个位置的值更新为 l - i,同时更新包含这个点的区间的最小值.
2.判断有没有以当前这个位置为左端点的查询区间,如果有,就在线段树中查找这个区间里面的最小值.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<list>
using namespace std;
const int maxn = ,INF = 0x7fffff;
map<int,int> mp; int n,m,A[maxn];
struct node
{
int d,l,r;
}tree[*maxn];
struct Node
{
int flag,ans;
int l,r;
}Q[maxn];
bool cmp(Node a,Node b)
{
return a.l >= b.l;
}
void maketree(node *tree,int p)
{
if(tree[p].l == tree[p].r)
{
tree[p].d = INF;
return ;
}
int mid = (tree[p].l + tree[p].r) / ;
tree[*p].l = tree[p].l;
tree[*p].r = mid;
tree[*p+].l = mid + ;
tree[*p+].r = tree[p].r;
tree[*p].d = tree[*p+].d = INF;
maketree(tree,*p);
maketree(tree,*p+);
}
void update(node *tree,int p,int loc,int d)
{
if(tree[p].l == tree[p].r)
{
tree[p].d = min(tree[p].d,d);
return ;
}
int mid = (tree[p].l + tree[p].r) / ;
if(loc <= mid)
update(tree,*p,loc,d);
else update(tree,*p+,loc,d);
tree[p].d = min(tree[p].d,d);
}
int data_sear;
void search(node *tree,int p,int l,int r)
{
if(tree[p].l == l && tree[p].r == r)
{
data_sear = min(data_sear,tree[p].d);
return ;
}
int mid = (tree[p].l + tree[p].r) / ;
if(r <= mid) search(tree,*p,l,r);
else if(l <= mid && r > mid)
{
search(tree,*p,l,mid);
search(tree,*p+,mid+,r);
}
else if(l > mid) search(tree,*p+,l,r);
} bool cmp2(Node a,Node b)
{
return a.flag < b.flag;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i = ;i <= n;++i)
scanf("%d",&A[i]);
for(int i = ;i < m;++i)
{
scanf("%d%d",&Q[i].l,&Q[i].r);
Q[i].flag = i;
Q[i].ans = INF;
}
sort(Q,Q+m,cmp); //按照左端点排好序,方便下面二分查找
tree[].l = ;
tree[].r = n;
tree[].d = INF;
maketree(tree,); //构建好线段树
mp.clear();
int f = ; //指向当前的查询
for(int i = n;i >= ;--i)
{
if(mp[A[i]] != )
update(tree,,mp[A[i]],mp[A[i]]-i); //更新线段树
mp[A[i]] = i;
while(f < m && Q[f].l == i)
{
data_sear = INF;
search(tree,,Q[f].l,Q[f].r); //查询这个区间内的最小值
Q[f].ans = (data_sear <= n? data_sear:-);
f++;
}
}
sort(Q,Q+m,cmp2);
for(int i = ;i < m;++i)
printf("%d\n",Q[i].ans);
}
return ;
}