CF522D Closest Equals（线段树点修改+区间最小值+离线+思维）

• 当max_r<=r，直接返回区间最小值
• 当min_r  > r ，直接返回INF

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include
<map>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;++i) #define per(i,a,n) for(int i=n;i>=a;--i)
const int INF = 0x3f3f3f3f;
const int u=500010;
struct {
	int p,l,r,right,dat,add,rm;
} t[u*4];

int A[500010];
void build(int p,int l,int r) {
	t[p].l=l,t[p].r=r;
	if(l==r) {
		t[p].dat=A[l];
		t[p].right=l+A[l];
		t[p].rm=t[p].right;
		return ;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].dat=min(t[p*2].dat,t[p*2+1].dat);
	t[p].right=max(t[p*2].right,t[p*2+1].dat);
	t[p].rm=min(t[p*2].rm,t[p*2+1].rm);
}


int ask(int p,int l,int r) {
	if(l<=t[p].l&&r>=t[p].r&&t[p].rm>r){
		return 0x3f3f3f3f;
	}
	if(l<=t[p].l&&r>=t[p].r&&t[p].right<=r) { return t[p].dat; } if(t[p].l == t[p].r)return 0x3f3f3f3f; int mid=(t[p].l+t[p].r)>>1;
	int val=0x3f3f3f3f;
	if(l<=mid) val=min(ask(p*2,l,r),val); if(r>mid) val=min(ask(p*2+1,l,r),val);
	return val;
}

int a[500010];
map<int ,int>mp;

int main() {
	int n,k;
	memset(A,0x3f,sizeof(A));
	scanf("%d%d", &n,&k);
	rep(i,1,n) {
		scanf("%d", &a[i]);
	}
	per(i,1,n) {
		if(mp[a[i]] == 0) mp[a[i]] = i;
		else {
			A[i] = mp[a[i]]-i;
			mp[a[i]] = i;
		}
	}
	build(1,1,n);
	int l,r;
	rep(i,1,k){
		scanf("%d%d", &l, &r);
		int ans = ask(1,l,r);
		if(ans == INF)puts("-1");
		else printf("%d\n", ans);
	}
	return 0;
}

#include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      
<map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(int x) { if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int maxn=5e5+10;

struct SegmentTree {
	int l,r;
	int dat;
} t[maxn * 4];
void build(int p,int l,int r) { //build(1，1，n) 1为根节点
    t[p].l=l,t[p].r=r;
    if(l==r) {
        t[p].dat=INF;
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].dat=min(t[p*2].dat,t[p*2+1].dat);
}
void change(int p,int x,int v) { //change(1,x,v) 1为根节点
	if(t[p].l==t[p].r) {
		t[p].dat=v;
		return ;
	}
	int mid=(t[p].l+t[p].r)/2;
	if(x<=mid)change(p*2,x,v);
	else change(p*2+1,x,v);
	t[p].dat=min(t[p*2].dat,t[p*2+1].dat);
}
int ask(int p,int l,int r) { //ask(1,l,r) 1为根节点
	if(l<=t[p].l && r>=t[p].r)return t[p].dat;
	int mid=(t[p].l + t[p].r)/2;
	int val=INF;
	if(l<=mid)val=min(val,ask(p*2,l,r)); if(r>mid) val=min(val,ask(p*2+1,l,r));
	return val;
}
int a[maxn];
int nxt[maxn];
int pre[maxn];
int ans[maxn];
map<int , int>mp;

struct ss {
	int l;
	int r;
	int pos;
	bool operator < (const ss &a) const {
		return l<a.l; } } seg[maxn]; int main() { int n,q; scanf("%d%d", &n, &q); build(1,1,n); rep(i,1,n) { scanf("%d", &a[i]); if(mp[a[i]]) { pre[i] = mp[a[i]]; nxt[mp[a[i]]] = i; change(1,i,i-pre[i]); } else { change(1,i,0x3f3f3f3f); } mp[a[i]]=i; } rep(i,1,q) scanf("%d%d",&seg[i].l,&seg[i].r),seg[i].pos=i; sort(seg+1,seg+q+1); int pos = 0; rep(index,1,q){ if(seg[index].l>pos){
			rep(i,pos,seg[index].l-1){
//				if(nxt[i]!=0)
				change(1,nxt[i],INF);
			}
			pos = seg[index].l;
		}
		int tmp = ask(1,seg[index].l,seg[index].r);
		if(tmp == INF) ans[seg[index].pos] = -1;
		else ans[seg[index].pos] = tmp;
	}
	rep(i,1,q){
		printf("%d\n", ans[i]);
	}
	return 0;
}