luoguP5283[12성 연합고사 2019]이종 또는 종자

#include
using namespace std;
#define re register
typedef long long ll;
const int maxn=5*1e5+10;
int n,m,tot;
int root[maxn],last[maxn*40*2];
int trie[maxn*40][2];
ll ans;
ll a[maxn],sum[maxn];
struct node
{
    int x,l,r,t;ll val;
    bool operatorq;
inline ll read()
{
    char c=getchar();ll res=0,f=1;
    while(c'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
void insert(int pre,int now,int t,ll k,int id)
{
    if(t<0){last[now]=id;return;}
    int c=(k>>t)&1;
    if(pre)trie[now][c^1]=trie[pre][c^1];
    trie[now][c]=++tot;
    insert(trie[pre][c],trie[now][c],t-1,k,id);
    last[now]=max(last[trie[now][0]],last[trie[now][1]]);
}
int query(int now,int t,ll k,int lim)
{
    if(t<0)return last[now];
    int c=(k>>t)&1;
    if(last[trie[now][c^1]]>=lim)return query(trie[now][c^1],t-1,k,lim);
    else return query(trie[now][c],t-1,k,lim);
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    n=read(),m=read();
    for(re int i=1;i<=n;i++)a[i]=read(),sum[i]=sum[i-1]^a[i];
    root[0]=++tot;last[0]=-1;insert(0,root[0],35,0,0);
    for(re int i=1;i<=n;i++)root[i]=++tot,insert(root[i-1],root[i],35,sum[i],i);
    for(re int i=1;i<=n;i++)
    {
        int pos=query(root[n],35,sum[i-1],i);
        //cerr<now.l)
        {
            int pos=query(root[now.t-1],35,sum[now.x-1],now.l);
            q.push((node){now.x,now.l,now.t-1,pos,sum[now.x-1]^sum[pos]});
        }
        if(now.t