自动搬运

查看原文

来自洛谷，原作者为

	ezoixx130 浴乎沂，风乎舞雩，咏而归

搬运于2025-08-24 22:04:28，当前版本为作者最后更新于2018-12-22 20:14:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

UPD：经评论区指正，时间复杂度应为 3 个 log。

看到题：单点插入？区间查询？线段树。异或和最大？线性基。

于是就可以线段树套线性基了。

线段树每个结点维护一个线性基，插入时直接插入，查询时把所有被查询区间所包含的区间的线性基插入到一个大的线性基里，最后在大的线性基里查询就好了。

时间复杂度 $O(n\log m\log ^2x)$

代码:

#include <bits/stdc++.h>
using namespace std;

struct lb
{
    int a[32];
    void insert(int x)
    {
        for(int i=31;i>=0;--i)
            if(x&(1<<i))
                if(a[i])x^=a[i];
                else
                {
                    a[i]=x;
                    return;
                }
    }
    void insert(lb &n)
    {
        for(int i=31;i>=0;--i)
            if(n.a[i])insert(n.a[i]);
    }
}p[200001];

void insert(int o,int l,int r,int k,int x)
{
    p[o].insert(x);
    if(l==r)return;
    int mid=(l+r)>>1;
    if(k<=mid)
        insert(o<<1,l,mid,k,x);
    else
        insert(o<<1|1,mid+1,r,k,x);
}

lb ans;

void query(int o,int l,int r,int ql,int qr)
{
    if(ql<=l && qr>=r){ans.insert(p[o]);return;}
    int mid=(l+r)>>1;
    if(qr<=mid)query(o<<1,l,mid,ql,qr);
    else if(mid<ql)query(o<<1|1,mid+1,r,ql,qr);
    else query(o<<1,l,mid,ql,mid),query(o<<1|1,mid+1,r,mid+1,qr);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        int op,a,b;
        scanf("%d%d%d",&op,&a,&b);
        if(op==1)insert(1,1,m,a,b);
        else
        {
            memset(ans.a,0,sizeof(ans.a));
            query(1,1,m,a,b);
            int maxn=0;
            for(int i=31;i>=0;--i)
                if((maxn^(ans.a[i]))>maxn)
                    maxn^=ans.a[i];
            printf("%d\n",maxn);
        }
    }
}