CF522D Closest Equals

CF522D Closest Equals

题目大意

现在有一个序列 \(a_1, a_2, ..., a_n\) ，还有\(m\)个查询 \(l_j, r_j\) \((1 ≤ l_j ≤ r_j ≤n)\) 。对于每一个查询，请找出距离最近的两个元素 \(a_x\) 和 \(a_y\)$ (x ≠ y)$ ，并且满足以下条件：

\(l_j ≤ x, y ≤ r_j\);

\(a_x = a_y\)。

两个数字的距离是他们下标之差的绝对值 \(|x − y|\) 。

分析

只有询问，考虑离线。同时我们需要知道每个数它前一个数的位置，再次想到离线。

但是，按照我们经常的操作，我们是对扫到的当前点进行操作，但是如果此时我们对当前点插入与上一个点的距离，则无法保证左端点一定在我们的询问范围内。因此我们进行调整，因为我们右端点是卡死的，因此如果我们是向上一个点插入与当前点的距离，则能保证两个点都一定在询问范围内。

这里对我们有一定的启发式意义。如果询问要求的两个点都在询问范围内，右端点一定在范围内，则我们只需要将需要维护的值维护到左端点上。

AC_code

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;

const int N = 5e5 + 10,INF = 0x3f3f3f3f;

struct Ask
{
    int l,r,id;
    bool operator<(const Ask& W) const
    {   
        return r<W.r;
    }
}ask[N];

struct Node
{
    int l,r,val;
}tr[N<<2];
unordered_map<int,int> pre;
int n,m,a[N],ans[N];

void build(int u,int l,int r)
{
    tr[u] = {l,r,INF};
    if(l==r) return ;
    int mid = l + r >> 1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}

void pushup(int u)
{
    tr[u].val = min(tr[u<<1].val,tr[u<<1|1].val);
}

void modify(int u,int x,int k)
{
    if(tr[u].l==tr[u].r)
    {
        tr[u].val = k;
        return ;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(x<=mid) modify(u<<1,x,k);
    else modify(u<<1|1,x,k);
    pushup(u);
}

int query(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r) return tr[u].val;
    int mid = tr[u].l + tr[u].r >> 1;
    int res = INF;
    if(l<=mid) res = min(res,query(u<<1,l,r)) ;
    if(r>mid) res = min(res,query(u<<1|1,l,r));
    return res;
}

int main()
{
    ios;cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(int i=0;i<m;i++)
    {
        int l,r;cin>>l>>r;
        ask[i] = {l,r,i};
    }
    sort(ask,ask+m);
    int now = 0;
    for(int i=0;i<m;i++)
    {
        int l = ask[i].l,r = ask[i].r,id = ask[i].id;
        while(now<r)
        {
            now++;
            if(pre.count(a[now])) modify(1,pre[a[now]],now-pre[a[now]]);
            pre[a[now]] = now;
        }
        int t = query(1,l,r);
        ans[id] = t==INF?-1:t;
    }
    for(int i=0;i<m;i++) cout<<ans[i]<<'\n';
    return 0;
}