宝石专家 离线
(n)个宝石带权值(a_i)从(1)排到(n)，(m)次询问，问区间([l,r])中权值相同的宝石的最近距离
离线做法的好题。
我们将所有询问按(r)排序，预处理出lp[i]，lp[i]表示与位置(i)上的宝石有相同权值的上一个宝石位置为(lp[i])，然后每次在区间([l,r])（(l,r)处是相同权值的宝石）的(r)处对线段树单点修改更新贡献(i-lp[i])（区间长度），线段树维护区间最小，每次查询即查([q[i].l,n])的区间最小值。因为已将询问按(r)排序，所以可以保证正确性。
具体还是看代码：
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int n,m;
inline int read(){
char ch=getchar();int s=0;
bool w=0;
while((ch<'0'||ch>'9')&&(ch!='-')) ch=getchar();
if(ch=='-'){w=1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+(ch^'0'),ch=getchar();
if(w) return -s;
return s;
}
#define MAXN 200002
int a[MAXN],a_sort[MAXN];
int idx[MAXN];
struct nod{
int l,r,id;
}q[MAXN];
int ans[MAXN];
bool cmp(const nod &a, const nod &b){
return a.r<b.r;
}
int s;
const int inf=1e9;
int tmp[MAXN];
int lp[MAXN];
int tre[MAXN*4];
#define sl (x<<1)
#define sr (x<<1|1)
void buildt(int x, int l, int r){
tre[x]=inf;
if(l==r) return;
int mid=(l+r)>>1;
buildt(sl, l, mid);
buildt(sr, mid+1, r);
}
void change(int x, int l, int r, int pos, int val){
if(l==r){
tre[x]=min(tre[x], val);
return;
}
int mid=(l+r)>>1;
if(pos<=mid) change(sl, l, mid, pos, val);
else change(sr, mid+1, r, pos, val);
tre[x]=min(tre[sl], tre[sr]);
}
int query(int x, int l, int r, int ql, int qr){
if(ql<=l&&r<=qr)
return tre[x];
int mid=(l+r)>>1;
int res=inf;
if(ql<=mid) res=min(query(sl, l, mid, ql, qr), res);
if(mid<qr) res=min(query(sr, mid+1, r, ql, qr), res);
return res;
}
int main() {
//freopen("jewel.in", "r", stdin);
//freopen("jewel.out", "w", stdout);
n=read(),m=read();
for(int i=1;i<=n;++i) a[i]=a_sort[i]=read();
sort(a_sort+1, a_sort+1+n);
s=unique(a_sort+1, a_sort+1+n)-a_sort;
for(int i=1;i<=n;++i) a[i]=lower_bound(a_sort+1, a_sort+1+s, a[i])-a_sort;
for(int i=1;i<=n;++i){
lp[i]=tmp[a[i]];
tmp[a[i]]=i;
}
buildt(1, 1, n);
for(int i=1;i<=m;++i) q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1, q+1+m, cmp);
int pos=1;
for(int i=1;i<=n;++i){
if(lp[i]!=0) change(1, 1, n, lp[i], i-lp[i]);
while(pos<=m&&q[pos].r==i){
ans[q[pos].id]=query(1, 1, n, q[pos].l, n);
++pos;
}
}
for(int i=1;i<=m;++i){
if(ans[i]==inf) puts("-1");
else printf("%d
", ans[i]);
}
return 0;
}