C++14(g++5.4) 解法, 执行用时: 509ms, 内存消耗: 28376K, 提交时间: 2019-10-12 16:44:17

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f;
#define lowbit( x ) (x&(-x))
int n , m , q, a[N] ,ans[N] ,c[N],pre[N<<2];
struct node{
	int L,R,id;
	bool operator < (const node &o) const{return L>o.L;}
}Q[N];
int add(int x,int v)
{
	for(;x<=n;x+=lowbit(x)) c[x] = min(c[x],v);
}
int ask(int x )
{
	int res = inf;
	for(;x>0;x-=lowbit(x)) res = min(res,c[x]);
	return res;
}
int main () {
	scanf("%d%d",&n,&q);
	for ( int i = 1 ; i <= n ; i ++ ) {
		scanf("%d",&a[i]);
		a[i]^=a[i-1];
	}
	for(int i=0;i<=n;i++) c[i] = inf ;
	for(int i = 1;i<=q;i++) {
		scanf("%d%d",&Q[i].L,&Q[i].R);
		--Q[i].L;
		Q[i].id = i;
	}
	sort(Q+1,Q+q+1);
	int cur = 1;
	for(int i=n;i>=0;i--)
	{
		if(pre[a[i]]){ add(pre[a[i]],pre[a[i]]-i);}
		pre[a[i]]=i;
		while(cur<=q&&Q[cur].L==i) {
			ans[Q[cur].id] = ask(Q[cur].R);
			if(ans[Q[cur].id]==inf) ans[Q[cur].id] = -1;
			++cur;
		}
	}
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 361ms, 内存消耗: 24548K, 提交时间: 2019-10-11 20:19:41

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+50;
int n,q,s[N],p[N],f[N],ans[N];
void cmin(int &x,int y){y<x?x=y:0;}
struct node{
    int l,r,id;
    bool friend operator <(node a,node b){return a.l>b.l;}
}Q[N];
void add(int x,int y){for(;x<=n;x+=x&-x)cmin(f[x],y);}
int ask(int x){int z=1e9;for(;x;x-=x&-x)cmin(z,f[x]);return z;}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1,x;i<=n;i++)scanf("%d",&x),s[i]=s[i-1]^x;
    for(int i=1;i<=q;i++)scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].l--,Q[i].id=i;
    memset(f,0x3f,sizeof(f));sort(Q+1,Q+q+1);
    for(int i=n,j=1;~i;i--){
        if(p[s[i]])add(p[s[i]],p[s[i]]-i);p[s[i]]=i;
        while(j<=q&&Q[j].l==i){
            int len=ask(Q[j].r);
            ans[Q[j].id]=len>n?-1:len;
            j++;
        }
    }
    for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
    return 0;
}