宝石专家

题目描述

Jim是一位宝石收藏品行家，在他的收藏室里保存着许多珍贵的宝石，磷叶石、钻石、摩根石、透绿柱石….，已知Jim有n个宝石，现在他将这n个宝石从1到n排开编号从1到n。Jim发现他所有的宝石中竟然有不少是完全相同的的，我们规定每个宝石都有一个特征值ai，当两个宝石特征值相等时及认为两个宝石相同。Jim发现两个相同的宝石离得越接近越明显。Jim现在有m个问题，他想问你在.编号l到r这一区间里的所有宝石中，两个相同宝石的最近距离是多少，（两个宝石的距离是它们编号的绝对值之差）。

保证 l < r ，对于 ax和ay 若ax=ay 它们的距离为|x-y|。

题意

就是询问有许多线段，每一个线段有权值，询问在区间[l,r]中线段的最小权值。

solution

把每一个线段与询问离线并按左排序，用2-pointer从大向小扫，保证对于询问时所有的线段是合法的。

然后使用线段树，询问 [0,r] 之间的最小值即可。

#include<bits/stdc++.h>
#define L first
#define R second
using namespace std;
int n;
int a[200100];
struct sgt{
    int val;
    int l, r;
}d[200100 << 2];
pair <int,int> p[200100]; int pl;
map <int,int> t;
int ans[200100];
int q;
struct qry{
    int id;
    int l, r;
    bool operator < (qry t){
        return l < t.l;
    }
}st[200100];
void build(int x,int l,int r){
    d[x].l = l, d[x].r = r;
    d[x].val = 0x3f3f3f3f;
    if (l == r) return;
    build(x<<1,l,(l+r)/2);
    build(x<<1|1,(l+r)/2+1,r);
}
void insert(int x,int p,int val){
    d[x].val = min(val, d[x].val);
    if (d[x].l == d[x].r) return;
    if (p <= d[x<<1].r) insert(x<<1,p,val);
    else insert(x<<1|1,p,val);
}
int query(int x,int p){
    if (d[x].l == d[x].r) return d[x].val;
    if (p <= d[x<<1].r) return query(x<<1,p);
    else return min(d[x<<1].val, query(x<<1|1,p));
}
int main(){
    cin >> n >> q;
    for (int i=1;i<=n;i++){
        scanf("%d", a+i);
        if (t.count(a[i])) p[++pl].L = t[a[i]], p[pl].R = i, t[a[i]] = i;
        else t[a[i]] = i;
    }
    for (int i=1;i<=q;i++){
        st[i].id = i;
        scanf("%d%d",&st[i].l,&st[i].r);
    }
    sort(p+1,p+pl+1);
    sort(st+1,st+q+1);
    int pl1 = pl;
    int pl2 = q;
    build(1,1,n);
    while (pl2 > 0){
        while (p[pl1].L >= st[pl2].l) insert(1,p[pl1].R,p[pl1].R-p[pl1].L), pl1--;
        ans[st[pl2].id] = query(1,st[pl2].r);
        pl2 --;
    }
    for (int i=1;i<=q;i++){
        printf("%d\n",(ans[i]==0x3f3f3f3f?-1:ans[i]));
    }
}