NC50444 老瞎眼 pk 小鲜肉（线段树 思维）

求q次询问下最短异或和为0子区间长度。

根据异或性质容易将条件转化为前缀和 sum[l-1]=sum[r] 的形式，用数组a记录一下前缀异或和最近出现的位置，则问题可以转化为维护单点贡献的形式。

考虑从1移动右端点，则随着右端的更新，将以此端点结尾的对应区间长度值赋给下标为左端点的求值数组，这样就可以使对区间的访问变为对左端点贡献的访问，询问答案即为对求值数组中区间 [l,r] 中最小值的查询，用线段树维护即可。

根据更新顺序，只能采用按r值从小到大的离线询问。

代码如下：

#include<bits/stdc++.h>
#define ls p<<1,l,mid
#define rs p<<1|1,mid+1,r
#define all 1,1,n
#define inf 0x3f3f3f3f
using namespace std;
const int nx=5e5+5;
int mp[1<<21]={1},a[nx],t[nx<<2];
int ans[nx],n,q;
struct node{
    int l,r,id;
    bool operator < (const node&oth) const{return r<oth.r;}
}seg[nx];
void up(int p,int l,int r,int x,int y){
    if(l==r){
        t[p]=y;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)up(ls,x,y);
    else up(rs,x,y);
    t[p]=min(t[p<<1],t[p<<1|1]);
}
int query(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y)return t[p];
    int mid=l+r>>1,re=inf;
    if(x<=mid)re=min(re,query(ls,x,y));
    if(mid<y)re=min(re,query(rs,x,y));
    return re;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1,x,y=0;i<=n;++i){
        scanf("%d",&x);
        y^=x;
        if(mp[y])a[i]=mp[y];
        mp[y]=i+1;
    }
    for(int i=0;i<q;++i)
        scanf("%d%d",&seg[i].l,&seg[i].r),seg[i].id=i;
    sort(seg,seg+q);
    memset(t,0x3f,sizeof t);
    int p=1;
    for(int i=0;i<q;++i){
        while(p<=seg[i].r){
            if(a[p])up(all,a[p],p-a[p]+1);
            ++p;
        }
        ans[seg[i].id]=query(all,seg[i].l,seg[i].r);
    }
    for(int i=0;i<q;++i)
        printf("%d\n",ans[i]==inf?-1:ans[i]);
}