题解 P4839 【P哥的桶】

ezoixx130 · 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);
        }
    }
}