题目链接：

http://codeforces.com/problemset/problem/522/D

D. Closest Equals

time limit per test3 seconds
memory limit per test256 megabytes
#### 问题描述
> You are given sequence a1, a2, ..., an and m queries lj, rj (1 ≤ lj ≤ rj ≤ n). For each query you need to print the minimum distance between such pair of elements ax and ay (x ≠ y), that:
>
> both indexes of the elements lie within range [lj, rj], that is, lj ≤ x, y ≤ rj;
> the values of the elements are equal, that is ax = ay.
> The text above understands distance as |x - y|.

输入

The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 5·105) — the length of the sequence and the number of queries, correspondingly.

The second line contains the sequence of integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109).

Next m lines contain the queries, one per line. Each query is given by a pair of numbers lj, rj (1 ≤ lj ≤ rj ≤ n) — the indexes of the query range limits.

输出

Print m integers — the answers to each query. If there is no valid match for some query, please print -1 as an answer to this query.

样例输入

5 3

1 1 2 3 2

1 5

2 4

3 5

样例输出

1

-1

2

题意

求区间内相邻最近的两个相同的数的距离。

题解

线段树，先处理出所有的相同的数的相邻的间隔区间，把这些区间（之后称为事件）按右端点排序，对于所有的查询区间也同样排序，然后一边扫查询，一边插入事件，事件按左端点插入，值为区间大小。

代码

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define X first

#define Y second

#define mkp make_pair

#define lson (o<<1)

#define rson ((o<<1)|1)

#define mid (l+(r-l)/2)

#define sz() size()

#define pb(v) push_back(v)

#define all(o) (o).begin(),(o).end()

#define clr(a,v) memset(a,v,sizeof(a))

#define bug(a) cout<<#a<<" = "<<a<<endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define scf scanf

#define prf printf

typedef long long LL;

typedef vector<int> VI;

typedef pair<int,int> PII;

typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;

const LL INFL=0x3f3f3f3f3f3f3f3fLL;

const double eps=1e-8;

const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=5e5+10;

int minv[maxn<<2];

int ql,qr,qmin;

void query(int o,int l,int r){

    if(ql<=l&&r<=qr){

        qmin=min(qmin,minv[o]);

    }else{

        if(ql<=mid) query(lson,l,mid);

        if(qr>mid) query(rson,mid+1,r);

    }

}

int _p,uv;

void update(int o,int l,int r){

    if(l==r){

        minv[o]=uv;

    }else{

        if(_p<=mid) update(lson,l,mid);

        else update(rson,mid+1,r);

        minv[o]=min(minv[lson],minv[rson]);

    }

}

struct Node{

    int l,r,v;

    Node(int l,int r,int v):l(l),r(r),v(v){}

};

bool cmp(const Node& n1,const Node& n2){

    return n1.r<n2.r;

}

map<int,int> mp;

int ans[maxn],arr[maxn],n,m;

void init(){

    rep(i,0,maxn<<2) minv[i]=INF;

}

int main() {

    scf("%d%d",&n,&m);

    init();

    vector<Node> lis;

    for(int i=1;i<=n;i++){

        scf("%d",&arr[i]);

        if(mp[arr[i]]){

            lis.pb(Node(mp[arr[i]],i,i-mp[arr[i]]));

        }

        mp[arr[i]]=i;

    }

//    rep(i,0,lis.sz()) prf("(%d,%d)\n",lis[i].l,lis[i].r);

    vector<Node> que;

    for(int i=0;i<m;i++){

        int l,r;

        scf("%d%d",&l,&r);

        que.pb(Node(l,r,i));

    }

    sort(all(lis),cmp);

    sort(all(que),cmp);

    int p=0;

    for(int i=0;i<que.sz();i++){

        while(p<lis.sz()&&lis[p].r<=que[i].r){

            _p=lis[p].l; uv=lis[p].v;

            update(1,1,n);

            p++;

        }

        ql=que[i].l,qr=que[i].r,qmin=INF;

        query(1,1,n);

        ans[que[i].v]=qmin>=INF?-1:qmin;

    }

    for(int i=0;i<m;i++) prf("%d\n",ans[i]);

    return 0;

}

//end-----------------------------------------------------------------------

巴特西

VK Cup 2015 - Qualification Round 1 D. Closest Equals 离线+线段树

题目链接：

D. Closest Equals

输入

输出

样例输入

样例输出

题意

题解

代码

最新文章

热门文章