【Codeforces Round #532 (Div. 2) F. Ivan and Burgers】离线+线性基

F. Ivan and Burgers

题意

n个数，q次询问，每次询问一个区间内选出任意个数的异或最大值。
$1<=n<=5?10^5$
$1<=q<=5?10^5$
做法

考虑离线的做法，首先将询问按照右端点排序，之后对于每个询问，将[1,R]范围内的数插入线性基，对于每个基保留最右面的并记录位置，由于线性基中只有log个元素，我们可以遍历一遍所有元素，取出在L之后的基构造最大值，便是答案。总复杂度$O(nlogn)$

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 5e5+5;
int a[maxn],pos[maxn];
bool insert_(int val,int p)
{
    for (int i=20;i>=0;i--){
    if (val&(1LL<<i)){
    if (!a[i]){
    a[i]=val;pos[i]=p;break;}if(pos[i]<p){
    swap(pos[i],p);swap(a[i],val);}val^=a[i];}}return val>0;
}
int query_max(int l)
{
    int ret=0;for (int i=20;i>=0;i--)if ((ret^a[i])>ret&&pos[i]>=l)ret^=a[i];return ret;
}
int c[maxn];
struct data
{
    int l,r,id;
}Q[maxn];
bool cmp(const data &a,const data &b)
{
    if(a.r==b.r) return a.l<b.l;return a.r<b.r;
}
int ans[maxn];
int main()
{
    int n,q;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&c[i]);scanf("%d",&q);for(int i=1;i<=q;i++){
    scanf("%d%d",&Q[i].l,&Q[i].r);Q[i].id=i;}sort(Q+1,Q+1+q,cmp);int r=1;for(int i=1;i<=q;i++){
    while(r<=Q[i].r){
    insert_(c[r],r);r++;}ans[Q[i].id]=query_max(Q[i].l);}for(int i=1;i<=q;i++) printf("%d\n",ans[i]);return 0;
}