链接：https://ac.nowcoder.com/acm/contest/1114/E
来源：牛客网
题目：
老瞎眼有一个长度为 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”。
解题思路：预处理出对于每个位置i找到左边离i最近的位置j使得a[j]^a[j+1]^a[j+2]^……a[i]=0记为pre[i],将询问按r从小到大排序，然后从1-n处理每个位置，对于位置i，在线段树上将pre[i]的值更新为i-pre[i]+1,然后查询【Q[i].l，Q[i].r】的最小值
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=5e5+6; int n,q; int pos[maxn<<2],pre[maxn],tree[maxn<<2],ans[maxn]; struct node{ int l,r,id; bool operator<(const node x)const{ return r<x.r; } }Q[maxn]; void update(int pos,int val,int l,int r,int rt){ if(l==r){ tree[rt]=min(tree[rt],val); return; } int mid=(l+r)>>1; if(pos<=mid) update(pos,val,l,mid,rt<<1); else update(pos,val,mid+1,r,rt<<1|1); tree[rt]=min(tree[rt<<1],tree[rt<<1|1]); } int query(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r){ return tree[rt]; } int ans=0x3f3f3f3f,mid=(l+r)>>1; if(L<=mid) ans=min(ans,query(L,R,l,mid,rt<<1)); if(R>mid) ans=min(ans,query(L,R,mid+1,r,rt<<1|1)); return ans; } int main(){ scanf("%d%d",&n,&q); int sum=0; for(int i=1;i<=4*500000;i++){ pos[i]=-1; tree[i]=0x3f3f3f3f; } pos[0]=0; for(int i=1;i<=n;i++){ int x; scanf("%d",&x); sum^=x; if(pos[sum]!=-1){ pre[i]=pos[sum]+1; }else pre[i]=-1; pos[sum]=i; } 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); int cnt=1; for(int i=1;i<=n;i++){ if(pre[i]!=-1) update(pre[i],i-pre[i]+1,1,n,1); while(Q[cnt].r==i){ ans[Q[cnt].id]=query(Q[cnt].l,Q[cnt].r,1,n,1); cnt++; } } for(int i=1;i<=q;i++){ if(ans[i]>n)puts("-1"); else printf("%d ",ans[i]); } return 0; }