题解 CF1100F 【Ivan and Burgers】

whiteqwq · 2020-10-25 19:49:31 · 题解

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;
}