Codeforces 522D Closest Equals

题意：给你一个序列和m个询问，问你序列中值想等距离最近的长度为多少。
解题思路：线段树+扫描线 +map(上一次出现的位置).
解题代码：
  1 // File Name: 522d.cpp
  2 // Author: darkdream
  3 // Created Time: 2015年03月12日 星期四 14时09分15秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 #define LL long long
 25 #define maxn 500005
 26 using namespace std;
 27 struct que{
 28   int l , r,si; 
 29 }qu[maxn];
 30 struct node{
 31   int l , r  ,m ; 
 32   int v; 
 33 }tree[maxn*4];
 34 int ans[maxn];
 35 int L(int x)
 36 {
 37    return 2 * x; 
 38 }
 39 int R(int x )
 40 {
 41    return 2 * x+ 1; 
 42 }
 43 void build(int c, int l, int r)
 44 {
 45     tree[c].l = l ; 
 46     tree[c].r = r; 
 47     tree[c].m = (l + r) >>1;
 48     tree[c].v = maxn +1000 ;
 49     if(tree[c].l == tree[c].r)
 50     {
 51        return ;
 52     }
 53     build(L(c),tree[c].l ,tree[c].m);
 54     build(R(c),tree[c].m+1,tree[c].r);
 55 }
 56 void push_up(int c)
 57 {
 58      tree[c].v = min(tree[L(c)].v,tree[R(c)].v);
 59 }
 60 void update(int c, int p,int v)
 61 {
 62      if(tree[c].l == tree[c].r && tree[c].l == p)
 63      {
 64        tree[c].v = v;
 65        return ;
 66      }
 67      if(p <= tree[c].m)
 68          update(L(c),p,v);
 69      else update(R(c),p,v);
 70      push_up(c);
 71 }
 72 int mi;
 73 void findans(int c, int l ,int r )
 74 {
 75     if(l <= tree[c].r && r >= tree[c].r)
 76     {
 77         mi = min(mi,tree[c].v);
 78         return;
 79     }
 80     if(l <= tree[c].m)
 81         findans(L(c),l,r);
 82     if(r > tree[c].m)
 83         findans(R(c),l,r);
 84 }
 85 map<int ,int>mp;
 86 int a[maxn];
 87 int cmp(que a, que b)
 88 {
 89    return a.l > b.l;
 90 }
 91 int main(){
 92    int n , m ; 
 93    scanf("%d %d",&n,&m);
 94    build(1,1,n);
 95    for(int i = 1;i <= n;i ++)
 96    {
 97       scanf("%d",&a[i]);
 98    }
 99    for(int i = 1;i <= m;i ++)
100    {
101       scanf("%d %d",&qu[i].l,&qu[i].r);
102       qu[i].si = i ;
103    }
104    sort(qu+1,qu+1+m,cmp);
105    int t = 1; 
106    for(int i = n;i >= 1;i --)
107    {
108        if(mp[a[i]])
109        {
110           //printf("%d %d
",mp[a[i]],mp[a[i]]-i);
111           update(1,mp[a[i]],mp[a[i]]-i);
112        }
113         mp[a[i]] = i ;
114        while(qu[t].l == i)
115        {
116           mi = maxn + 1000;
117           findans(1,qu[t].l,qu[t].r);
118           if(mi == maxn + 1000 )
119               mi = -1;
120           ans[qu[t].si] = mi;
121           t ++; 
122        }
123    }
124    for(int i = 1;i <= m;i ++)
125        printf("%d
",ans[i]);
126 return 0;
127 }
View Code
没有梦想，何谈远方