线性基

https://ac.nowcoder.com/acm/contest/81/E

正好打比赛遇到了就顺便试一试牛客的博客功能~感觉这个风格还是比较舒服的~

线性基用来处理异或和问题，可以log时间判断一段区间内异或和的最大最小值以及是否可以异或出某个数。

线性基所用到的思想类似于可以用10个数来表示0~1023

我们用一个数组a表示线性基，数组的每一位储存二进制最高位是这一位的一个数，意味着我们可以用这个数把这一位异或成1。每次插入一个数的时候我们查找线性基里这个数最高位这一位是否有数字，没有的话就插入在这里，有的话我们用这个已有数和新数字进行异或，再尝试插入新的数字，因为新的数字的最高位也是可以异或出来的。

可能描述起来非常抽象，但是大家看一下代码就发现其实非常简单啦~

插入

void insert(int val)
{
    for(int i=31;i>=1;i--)
    {
        int j=i-1;
        if(val&(1<<j))
        {
            if(!a[i])
            {
                a[i]=val;
                break;
            }
            val^=a[i];
        }
    }    
    if(val==0)  a[0]=1;    
}

查找

int fin(int val)
{
    if(val==0&&a[0])  return 1;    for(int i=31;i>=1;i--)    {      int j=i-1;      if(val&(1<<j))      {      val^=a[i];        if(!val)  return 1;      }    }    return 0;
}

最大最小

int finmax()
{    int ans=0;    for(int i=31;i>=1;i--)    {      if((ans^a[i])>ans)   ans^=a[i];    }    return ans;
}
int finmin()
{    if(a[0])  return 0;    for(int i=1;i<=31;i++)    {      if(a[i])   return a[i];    }    return 0;
}

怎么样，是不是超简单！

来看看一道例题吧~

E-无效位置

https://ac.nowcoder.com/acm/contest/81/E

题意很容易理解，难点主要在于线性基很容易插入、合并，但是没法完成删除操作。于是想到从后往前操作，将删点转化为从后往前插入。剩下的就很简单啦~下面是代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<time.h>
#include<climits>
using namespace std;
#define fi first
#define se second
#define Chtholly_is_so_cute ios::sync_with_stdio(false);cin.tie(0);
#define pb push_back
#define Max(x,y) (x>y?x:y)
#define Min(x,y) (x<y?x:y)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define debug(x) printf("# %d\n",x)
typedef long long LL;
typedef unsigned long long uLL;

#define linear_base LB
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int gcd(int a, int b)
{     return b?gcd(b,a%b):a;
}


struct linear_base 
{     int a[33];     void insert(int val)     {         for(int i=31;i>=1;i--)         {             int j=i-1;             if(val&(1<<j))             {                 if(!a[i])                 {                     a[i]=val;                     break;                 }                 val^=a[i];             }         }         if(val==0)    a[0]=1;     }     int fin(int val)     {         if(val==0&&a[0])    return 1;         for(int i=31;i>=1;i--)         {             int j=i-1;             if(val&(1<<j))             {                 val^=a[i];                 if(!val)    return 1;             }         }         return 0;     }     int finmax()     {         int ans=0;         for(int i=31;i>=1;i--)         {             if((ans^a[i])>ans)    ans^=a[i];         }         return ans;     }     int finmin()     {         if(a[0])    return 0;         for(int i=1;i<=31;i++)         {             if(a[i])    return a[i];         }         return 0;     }
}e[MAXN];

void merge(LB &a, LB &b)
{     for(int i=31;i>=1;i--)     {         if(b.a[i]==0)    continue;         a.insert(b.a[i]);     }     b=a;
}
int a[MAXN];
struct Node
{     int l,r;     int val;
}b[MAXN];
int x[MAXN];
stack<int> sta;
void solve()
{     //Chtholly_is_so_cute     int n;     scanf("%d",&n);     for(int i=1;i<=n;i++)         scanf("%d",&a[i]);     for(int i=1;i<=n;i++)         scanf("%d",&x[i]);     memset(b,-1,sizeof(b));     int ans=0;     for(int i=n;i>=1;i--)     {         int pos=x[i];         b[pos].val=a[pos];         e[pos].insert(b[pos].val);         b[pos].l=pos,b[pos].r=pos;         if(pos+1<=n&&b[pos+1].val!=-1)         {             merge(e[pos],e[pos+1]);             b[b[pos].l].r=b[pos+1].r;             b[b[pos+1].r].l=b[pos].l;             e[b[pos].l]=e[pos];             e[b[pos+1].r]=e[pos];         }         if(pos-1>=1&&b[pos-1].val!=-1)         {             merge(e[pos],e[pos-1]);             b[b[pos].r].l=b[pos-1].l;             b[b[pos-1].l].r=b[pos].r;             e[b[pos].r]=e[pos];             e[b[pos-1].l]=e[pos];         }         ans=Max(ans,e[pos].finmax());         sta.push(ans);     }     while(!sta.empty())     {         printf("%d\n",sta.top());         sta.pop();     }
}
int main()
{     solve();     return 0;
}