线性基
线性基是什么？
是一个数的集合。
原数组中的每个数都可以由这个集合里的树异或得到。
也就是原数组的压缩。
学习参考：
大佬博客
b站视频
性质
1、原数组里的数可以由线性基里的数异或得到。所以原数组里的一些数的异或也可以由线性基里的一些数异或得到。
2、线性基里的任意数异或起来都不可能为0，
3、线性基里的数的个数是确定的，满足性质的前提下是最少的。（插入顺序改变但是线性基里的数的个数不会变）
（抄自大佬博客）
插入一个数：
int b[35];
bool add(int x)
{
for (int i = 30; i >= 0; i -- )
{
if(x & (1 << i))
{
if(b[i])
{
x ^= b[i];
}
else
{
b[i] = x;
return true;
}
}
}
return false;
}
也就是二进制下每一位上面找个代表。。
怎么说呢？
就是 比如要插入：111111111 101010 11 10 这几个数（二进制下的）
然后
b[9]： 111111111
b[6]： 101010
b[2]： 11
b[1]： 1
就是这样子的。。
bool类型返回的意思是这个数有没有插入进去
为什么有没插入进去的情况？
因为如果数组里已经有了
b[i] b[j] 如果这个x就等于b[i] ^ b[j] 就没有插入进去
可以看出来在int的范围下最多有31个数，， 大大压缩了数据范围。
找异或最大值
比如询问数组中随便选出来一些数的异或的最大值是多少？
可以在线性基上贪心的选
int query()
{
int ans =0 ;
for (int i = 30; i >= 0; i -- )
{
if(b[i])
{
ans = max(ans,ans ^ b[i]);
}
}
return ans;
}
求最小值
比如询问数组中随便选出来一些数的异或的最小值是多少？
如果有数不能***去 那么答案就是0，否则就是最小的b[i] .
这个很好想。因为最小的b[i]异或别的数一定会变大
求异或第k小的值
比如询问数组中随便选出来一些数的异或的第k小值是多少？
怎么求？先处理一下数组
比如刚开始的线性基是这个样子。
b[9]： 111111111
b[6]： 101010
b[2]： 11
b[1]： 1
让他变成这个样子:
b[9]： 110101100
b[6]： 101001
b[2]： 10
b[1]： 1
就是说让他变得最小。。
怎么处理呢?
int temp[35];
int cnt =0 ;
void init()
{
for (int i = 1; i <= 30; i ++ )
{
if(b[i])
{
for (int j = i- 1; j >= 0; j -- )
{
if(b[i] & (1 << j))
{
b[i] ^= b[j];
}
}
}
}
for (int i = 0; i <= 30;i ++ )
{
if(b[i])
temp[cnt ++ ] = b[i];
}
}
然后得到一个新的线性基。
如果要求第10大 10的二进制是1010 于是答案就是temp[3] ^ temp[1]。
对了，，还有一点，就是如果有0得先减去0的个数，如果有数插不进去，也是0.
区间线性基怎么搞？
比如要求l~r里的线性基
b[maxn][35]
可以再加一个数组pos[maxn][30]
表示这个数是来自第几个数。
从第i个数到第i + 1个数怎么变？
先把b[i]复制到b[i + 1]里面
pos[i] 复制到pos[i+1]里面，
然后往里面插入x就得到了1~i+1里的线性基。
但是要找l~r里的现在可以得到1到r里的怎么排除1到l-1里的呢？
就是插入的时候如果这个数就是 靠右插入的数尽可能在高位出现
bool add(int x,int num)
{
int p = x;
for (int i = 0; i <= 30; i ++ )
{
b[x][i] = b[x - 1][i];
pos[x][i] = pos[x - 1][i];
}
for (int i = 30; i >= 0; i -- )
{
if(num & (1 << i))
{
if(b[x][i])
{
if(pos[x][i] < p)
{
swap(num,b[x][i]);
swap(pos[x][i],p);
}
num ^= b[x][i];
}
else
{
b[x][i] = num;
pos[x][i] = p;
return true;
}
}
}
return false;
}
然后pos只有在l~r区间里的时候就可以算上
hdu6579
就算是一个区间线性基最大异或的板子吧。。
代码:
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <set>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
int b[maxn][32];
int pos[maxn][32];
bool add(int x,int num)
{
int p = x;
for (int i = 0; i <= 30; i ++ )
{
b[x][i] = b[x - 1][i];
pos[x][i] = pos[x - 1][i];
}
for (int i = 30; i >= 0; i -- )
{
if(num & (1 << i))
{
if(b[x][i])
{
if(pos[x][i] < p)
{
swap(num,b[x][i]);
swap(pos[x][i],p);
}
num ^= b[x][i];
}
else
{
b[x][i] = num;
pos[x][i] = p;
return true;
}
}
}
return false;
}
int getans(int l,int r)
{
int ans = 0;
for (int i = 30; i >= 0; i -- )
{
if(b[r][i])
{
if(pos[r][i] >= l && pos[r][i] <= r)
{
ans = max(ans,ans ^ b[r][i]);
}
}
}
return ans;
}
void init()
{
memset(b,0,sizeof(b));
memset(pos,0,sizeof(pos));
}
int main()
{
int T;
scanf("%d",&T);
while(T -- )
{
init();
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i ++ )
{
int x;
scanf("%d",&x);
add(i,x);
}
int la = 0;
while(m -- )
{
int f;
scanf("%d",&f);
if(f)
{
int x;
scanf("%d",&x);
x ^= la;
n ++ ;
add(n,x);
}
else
{
int l,r;
scanf("%d%d",&l,&r);
l = (l ^ la) % n + 1;
r = (r ^ la) % n + 1;
// printf("%d %d\n",l,r);
if(l > r)
swap(l,r);
la = getans(l,r);
printf("%d\n",la);
}
}
}
}
京公网安备 11010502036488号