传送门

 　　题目大意：给你一个长度为n的数组，要求你在其中找到一个长度最短的连续子序列使得它们的异或和不小于k。如果有多个符合要求的序列，则输出左端点最小的。

　　

　　根据异或的性质，我们很容易想到异或前缀和快速计算一个区间的异或和。如何快速判断是否有一个数与选中的数异或后不小于k呢？我们可以考虑使用二进制字典树。枚举r，使用二进制字典树维护最大的l。每一次先查询最大的l能与当前r匹配，更新答案，再将r插入字典树。

　　完整AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <vector>
#include <queue>
#include <map>
#define INF 999999999
using namespace std;
typedef long long ll;

int t,n,k;
int a[100005],b[100005];
int val[6400005],wei[6400005],trie[6400005][2],nex;

void init()
{
    for(int i=0;i<=nex+1;i++)
    {
        val[i]=wei[i]=trie[i][0]=trie[i][1]=0;
    }
    wei[0]=30;
}

void build(int x,int v)
{
    int ni=0;
    for(int i=30;i>=0;i--)
    {
        int xi=(x&(1<<i))?1:0;
        if(!trie[ni][xi]) trie[ni][xi]=++nex;
        ni=trie[ni][xi];
        val[ni]=v;
        wei[ni]=i-1;
    }
}

int check(int x,int ni)
{
    int ans=-1,xi=(x&(1<<wei[ni]))?1:0;
    int ki=(k&(1<<wei[ni]))?1:0;
    if(wei[ni] == -1)
    {
        if(ki > xi)
        {
            return -1;
        }
        else 
        {
            return val[ni];
        }
    }
    if(ki)
    {
        if(trie[ni][!xi])
        {
            ans=check(x,trie[ni][!xi]);
        }
    }
    else
    {
        if(trie[ni][xi])
        {
            ans=max(ans,check(x,trie[ni][xi]));
        }
        if(trie[ni][!xi])
        {
            ans=max(ans,val[trie[ni][!xi]]);
        }
    }
    return ans;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        init();
        nex=0;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            b[i]=b[i-1]^a[i];
        }
        int l=-1,r=INF;
        for(int i=1;i<=n;i++)
        {
            build(b[i],i);
            int tem=check(b[i],0);
            if(tem != -1 && i-tem < r-l+1)
            {
                l=tem+1;
                r=i;
            }
        }
        if(r == INF)
        {
            cout<<-1<<endl;
        }
        else
        cout<<l<<" "<<r<<endl;
    }
}