CF1100F Ivan and Burgers解题报告

解题报告

CF1100F Ivan and Burgers解题报告：

更好的阅读体验

题意

• 给定长度为$n$的序列$c$，$q$次询问，每次求$l$到$r$选取任意个数异或和最大是多少。
• 数据范围：$1\leqslant n,m\leqslant 5\times 10^5,1\leqslant c_i\leqslant 10^6$。

分析

这道题的测试点数是真的多。。。

一道猫树分治+线性基题。

猫树分治的操作：从区间$[l,r]$中选一个分治中点$mid$，预处理$[l,mid]$的信息，预处理$[mid,r]$的信息，然后对所有跨越了$mid$的询问快速合并，不经过$mid$直接向子区间分治。

这道题我们可以直接把询问离线，然后上猫树分治。

具体地，我们用$O(\log c)$的暴力预处理$[a,mid]$和$[mid,b]$的线性基（其中$a\in[l,mid],b\in[mid,r]$），然后在合并的时候用$O(\log^2 c)$的暴力合并跨越$mid$的两个线性基。

总复杂度：$O(n\cdot\log n\cdot \log c+q\cdot\log^2 c)$。

代码

#include<stdio.h>
const int maxn=500005,maxm=500005,maxk=31;
int n,m;
int a[maxn],ans[maxm];
struct question{//询问
    int l,r,id;
}q[maxm],tmp1[maxm],tmp2[maxm];
struct base{//线性基
    int p[maxk];
    void clear(){
        for(int i=0;i<maxk;i++)
            p[i]=0; 
    }
}b[maxn];
void insert(base &now,int x){//线性基插入
    for(int i=30;i>=0;i--){
        if(((x>>i)&1)==0)
            continue;
        if(now.p[i]==0){
            now.p[i]=x;
            return ;
        }
        x^=now.p[i];
    }
}
base merge(base a,base b){//线性基合并
    for(int i=0;i<=30;i++)
        if(b.p[i])
            insert(a,b.p[i]);
    return a;
}
int getmax(base x){//线性基求异或最大值
    int res=0;
    for(int i=30;i>=0;i--)
        if((res^x.p[i])>res)
            res^=x.p[i];
    return res;
}
void solve(int l,int r,int ql,int qr){//猫树分治
    if(ql>qr)
        return ;
    if(l==r){
        for(int i=ql;i<=qr;i++)
            ans[q[i].id]=a[l];
        return ;
    }
    int mid=(l+r)>>1,cnt1=0,cnt2=0;
    b[mid].clear(),insert(b[mid],a[mid]);
    for(int i=mid-1;i>=l;i--)
        b[i]=b[i+1],insert(b[i],a[i]);
    for(int i=mid+1;i<=r;i++)
        b[i]=b[i-1],insert(b[i],a[i]);
    for(int i=ql;i<=qr;i++){//合并左右预处理过的线性基
        if(l<=q[i].l&&q[i].l<=mid&&mid+1<=q[i].r&&q[i].r<=r){
            ans[q[i].id]=getmax(merge(b[q[i].l],b[q[i].r]));
            continue;
        }
        if(q[i].l<=mid&&q[i].r<=mid)
            tmp1[++cnt1]=q[i];
        else tmp2[++cnt2]=q[i];
    }
    for(int i=1;i<=cnt1;i++)
        q[ql+i-1]=tmp1[i];
    for(int i=1;i<=cnt2;i++)
        q[ql+cnt1+i-1]=tmp2[i];
    solve(l,mid,ql,ql+cnt1-1),solve(mid+1,r,ql+cnt1,ql+cnt1+cnt2-1);//分治解决子问题
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    solve(1,n,1,m);
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}