CF1100F Ivan and Burgers 记录

· · 题解

题意：给定一个数列，每次询问一个区间中选取一些数的异或最大值，可以离线，n\le 5\times10^5。

显然 3\log 跑不过去，考虑 2\log 做法。

思考一种神秘的对整体二分的做法。

对值域 [1,n] 二分，记录 mid=\lfloor\frac{1+n}{2}\rfloor，把 r 小于 mid 的询问分到左边，把 l 大于 mid 的询问分到右边，再处理掉经过 mid 的询问，对于这一个的处理，可以记录从 mid 开始的前缀线性基和后缀线性基，这样复杂度一层就是 O(n\log n) 总时间复杂度就是 O(n\log^2n)。

现在是 21:20，我看我什么时候写完。

现在是 21:39，我写完了。

#define maxn 500010
struct xxj{
    #define Maxbit 21
    #define _Tp int
    _Tp p[Maxbit+1];
    void insert(_Tp x){
      if(!x)return;
        for(int i=Maxbit;i+1;i--){
            if(!(x>>i))continue;
            if(!p[i]){p[i]=x;break;}
            x^=p[i];
        }
    }
    void clear(){memset(p,0,sizeof p);}
    void insert(xxj h){for(int i=0;i<=Maxbit;i++)insert(h.p[i]);}
    _Tp ask(){
        _Tp ans=0;
        for(int i=Maxbit;i+1;i--)
        if((ans^p[i])>ans)ans^=p[i];
        return ans;
    }
}st[maxn];
int n,m;
int a[maxn];
struct prpr{
    int l,r,id;
}q[maxn],tmpl[maxn],tmpr[maxn];
int Ans[maxn];
int work(xxj a,xxj b){
    return a.insert(b),a.ask();
}
void solve(int l,int r,int L,int R){
    if(L>R)return;
    if(l==r){
        for(int i=L;i<=R;i++)Ans[q[i].id]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    st[mid].clear();
    st[mid].insert(a[mid]);
    for(int i=mid-1;i>=l;i--)st[i]=st[i+1],st[i].insert(a[i]);
    for(int i=mid+1;i<=r;i++)st[i]=st[i-1],st[i].insert(a[i]);
    int ll=0,rr=0;
    for(int i=L;i<=R;i++){
        if(q[i].r<mid)tmpl[++ll]=q[i];
        else if(q[i].l>mid)tmpr[++rr]=q[i];
        else Ans[q[i].id]=work(st[q[i].l],st[q[i].r]);
    }
    for(int i=1;i<=ll;i++)q[L+i-1]=tmpl[i];
    for(int i=1;i<=rr;i++)q[L+ll+i-1]=tmpr[i];
    solve(l,mid,L,L+ll-1);
    solve(mid+1,r,L+ll,L+ll+rr-1);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("testdata.in","r",stdin);
#endif
    cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;for(int i=1;i<=m;i++)cin>>q[i].l>>q[i].r,q[i].id=i;
    solve(1,n,1,m);
    for(int i=1;i<=m;i++)cout<<Ans[i]<<endl;
#ifndef ONLINE_JUDGE
    cerr<<endl<<(double)clock()/CLOCKS_PER_SEC;
#endif
}

合并时千万要把两个线性基合并起来再计算，不能不合并，like this

int ans=0;
for(int i=21;i+1;i--)if((ans^a.p[i])>ans)ans^=a.p[i];
for(int i=21;i+1;i--)if((ans^b.p[i])>ans)ans^=b.p[i];
return ans;