D. Closest Equals_牛客博客

CF 522D

最多存在 $n$ 个数对会贡献答案

就是每个数和前面第一个和自己相同的数,把下标记作 $pre[x]$

那么想象一下,现在要统计 $[l,r]$ 的最短相同数对距离

我们可以直接对所有 $[1,r]$ 的 $i-pre[i]$ 投射到线段树上去

线段树上的下标就是 $pre[x]$ ,值就是 $i-pre[x]$

这样我们查询 $[l,r]$ 的最小值,查到的所有 $i-pre[x]$ 的 $i$

都属于 $[l,r]$ ,而 $pre[x]$ 由于是下标,所以也肯定满足

由于每个区间只需要 $[1,r]$ 的数插入,所以按照 $r$ 端点排序

这样每个点只需要插入一次,非常快

非常巧妙的思路

关于找前一个相同的数,可以用 $map$ ,也可以离散化

#include <bits/stdc++.h>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
const int maxn=2e6+10;
const int inf=1e9;
int a[maxn],b[maxn],n,m,ans[maxn];
map<int,int>mp;
struct p{
    int l,r,id;
    bool operator < (const p&tmp )    const
    {    return r<tmp.r; }
}f[maxn]; int top=1;
void update(int rt,int l,int r,int u,int val)
{
    if( l==r&&l==u ){ a[rt]=val; return; }
    if( r<u||l>u )    return;
    update(lson,u,val); update(rson,u,val);
    a[rt] = min( a[ls],a[rs] );
}
int ask(int rt,int l,int r,int L,int R)
{
    if( l>=L&&r<=R )    return a[rt];
    if( r<L||l>R )    return inf;
    return min( ask(lson,L,R),ask(rson,L,R) );
}
int main()
{
    cin >> n >> m;
    for(int i=1;i<=4*n;i++)    a[i]=inf;//线段树初始化 
    for(int i=1;i<=n;i++)    cin >> b[i];
    for(int i=1;i<=m;i++)    scanf("%d%d",&f[i].l,&f[i].r),f[i].id=i;
    sort(f+1,f+1+m);
    for(int i=1;i<=n;i++)
    {
        if( mp[b[i]] )    update(1,1,n,mp[b[i]],i-mp[b[i]]);
        while( top<=m&&i==f[top].r )
            ans[f[top].id]=ask(1,1,n,f[top].l,f[top].r),top++;
        mp[b[i]]=i;    
    }
    for(int i=1;i<=m;i++)
        cout << ( ans[i]==inf?-1:ans[i] ) << '\n';
}