题目描述
老瞎眼有一个长度为 n 的数组 a,为了为难小鲜肉，他准备了 Q 次询问，每次给出 一个区间[L,R],他让小鲜肉寻 找一对 l,r 使L<=l<=r<=R 且 a[l]a[l+1]a[l+2]…^a[r]=0,老瞎眼只让他回答r-l+1 最小是多少，若没有符合条件的 l,r 输出”-1”。

输入描述:
第一行输入 n,Q。
第二行输入 n 个数，表示 a 数组。
接下来 Q 行，每行输入 L,R。
1<=n,Q<=500000,0<=a[i]<=1000000,1<=L<=R<=n

输出描述:
若有解，输出 r-l+1 最小是多少。
否则输出“-1”。

示例1
输入
复制

4 2
2 1 3 3
1 2
1 3

输出
复制

-1
3

说明
第一次询问无解。
第二次询问:
l=1,r=3

刚看到题目时，没有想到怎么去维护区间最近的位置。

我们如果考虑离线去做，把区间按照右端点排序。

我们提前预处理出数组的异或前缀和。然后我们对于某个区间异或为0，相当于就是前缀异或和中两个点的值相同。

然后我们按照右端点排序之后，保证当前查询的时候，右端点一定是保证满足的，然后我们看左端点的位置即可。所以我们插入元素时，插入到左端点即可。

然后用线段树一直维护区间的最小值。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e5+10;
const int inf=0x3f3f3f3f;
int n,Q,sum[N],vis[N<<2],ed,res[N];
struct query{
	int l,r,id;
}q[N];
struct node{
	int l,r,mi;
}t[N<<2];
int cmp(query a,query b){
	return a.r<b.r;
}
inline void push_up(int p){
	t[p].mi=min(t[p<<1].mi,t[p<<1|1].mi);
}
void build(int p,int l,int r){
	t[p].l=l; t[p].r=r; t[p].mi=inf;
	if(l==r)	return ;	int mid=l+r>>1;
	build(p<<1,l,mid); build(p<<1|1,mid+1,r);
}
void change(int p,int x,int v){
	if(t[p].l==t[p].r){
		t[p].mi=min(t[p].mi,v);	return ;
	}
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid)	change(p<<1,x,v);
	else	change(p<<1|1,x,v);
	push_up(p);
}
int ask(int p,int l,int r){
	if(t[p].l==l&&t[p].r==r)	return t[p].mi;
	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return ask(p<<1,l,r);
	else if(l>mid)	return ask(p<<1|1,l,r);
	else	return min(ask(p<<1,l,mid),ask(p<<1|1,mid+1,r));
}
signed main(){
	scanf("%d %d",&n,&Q);
	for(int i=1;i<=n;i++)	scanf("%d",&sum[i]);
	for(int i=1;i<=n;i++)	sum[i]^=sum[i-1];
	for(int i=1;i<=Q;i++)	scanf("%d %d",&q[i].l,&q[i].r),q[i].id=i;
	sort(q+1,q+1+Q,cmp);	ed=1;	build(1,0,n);
	memset(vis,-1,sizeof vis);	vis[0]=0;
	for(int i=1;i<=Q;i++){
		for(int j=ed;j<=q[i].r;j++){
			if(vis[sum[j]]!=-1)	change(1,vis[sum[j]],j-vis[sum[j]]);
			vis[sum[j]]=j;
		}
		ed=q[i].r+1;
		res[q[i].id]=ask(1,q[i].l-1,q[i].r);
		if(res[q[i].id]==inf)	res[q[i].id]=-1;
	}
	for(int i=1;i<=Q;i++)	printf("%d\n",res[i]);
	return 0;
}