线性基

线性基在一般被Acmer和Oier们用来处理区间异或问题

线性基

性质

对于一个数组，存在一些数构成该数组的线性基 线性基有三大很优美的性质

数组中所有数均可以由线性基中部分数异或得到数组中所有数异或出来均不为0对于同一数组线性基个数唯一 例如，$2，4，5，6$,由线性基$1,2,4$,数组所有数均可以由$1,2,4$异或得到

线性基构造

数组每加入一个数，对线性基进行修改 令线性基为$d[32]$,数组长度为$max(a[i])的最大二进制$（所有数均可以由$1,2,4\cdots ,2^n$表示）

void add(int x) { for(int i=31; i>=0; i--) { //i为线性基下标 if(x&(1<<i)) { if(d[i])x^=d[i]; //若该二进制位已有值，异或寻找线性基能否表达x^d[i] else { d[i]=x; //若二进制位没有值，说明x不能被线性基表达，令d[i]=x break; //记得如果插入成功一定要退出 } } } }

构造合理性：

若能插入$x$,则将$d[i]=x$,x可以由线性基表达若不能插入$x$,则$x$最终异或为0，即可以由线性基表达

区间异或最大值

数组$(L,R)$内取若干个数，使这些数异或后得到的值最大 令$d[32]$数组表示线性基的值，$p[32]$数组表示线性基的位置（为了便于询问，位置尽量存偏右的）

int ask(int l,int r){ int res=0; for（int i=31;i>=0;i--） if(p[i]>=l&&(res^d[i])>res) res^=d[i]; return res; }

贪心：高位能变成1，就变成1（高位1比低位都变成1都有价值）

异或最小值点

即为最小的d[i],很显然的结果

区间异或第k大

先将线性基处理成 $1,2,4,\cdots ,2^n$的二进制表达形式 去除为0的异或值，每一位$d[i]=1$相当于可以表达的二进制位数增加一位

void work() { //将线性基转化为2进制 for(int i=1; i<=31; i++) for(int j=1; j<=i; j++) if(d[i]&(1<<(j-1))) d[i]^=d[j-1]; } int k_th(int k) { if(k==1&&tot<n)return 0; //特判一下，假如k=1，并且原来的序列可以异或出0，就要返回0， //tot表示线性基中的元素个数，n表示序列长度 if(tot<n)k--; //类似上面，去掉0的情况，因为线性基中只能异或出不为0的解 work(); int ans=0; for(int i=0; i<=31; i++) if(d[i]!=0) { if(k&1)ans^=d[i]; k>>=1; } }

线性基的交链接

HDU6579 Operation 杭电多校第一场 1002

题意

两种操作$0x$表示在数组a最后添加一个数x，$1LR$询问$(L,R)$内的最大异或值

分析

添加： 对每一个$i$，维护数组$(1,i)$的线性基，且使$d[i]$的位置尽量靠右（大） 询问： 同上方的解释

代码

添加 注意当出现比d[x]位置更靠右的值，要将原有的d[x]换出来，寻找原d[x]能否产生更靠右的d[y]$(y<x)$

void add(int x, int value) { int t = x; for (int i = 30; i >= 0; i--) { if (value & (1 << i)) { if (!d[i]) { d[i] = value; pos[i] = x; break; } else if (pos[i] < x) { //将d[x]换出来 swap(d[i], value); swap(pos[i], x); } value ^= d[i]; } } for (int i = 0; i <= 30; i++) //存储值 v[t][i] = d[i], p[t][i] = pos[i]; }

完整代码

#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 1e6 + 5; int a[maxn], d[32], pos[32],v[maxn][32], p[maxn][32]; inline void init() { memset(d, 0, sizeof(d)); memset(pos, 0, sizeof(pos)); } void add(int x, int value) { int t = x; for (int i = 30; i >= 0; i--) { if (value & (1 << i)) { if (!d[i]) { d[i] = value; pos[i] = x; break; } else if (pos[i] < x) { swap(d[i], value); swap(pos[i], x); } value ^= d[i]; } } for (int i = 0; i <= 30; i++) v[t][i] = d[i], p[t][i] = pos[i]; } int ask(int l, int r) { int res = 0; for (int i = 30; i >= 0; i--) if (p[r][i] >= l && (res ^ v[r][i]) > res) res ^= v[r][i]; return res; } int main() { int t; scanf("%d", &t); while (t--) { init(); int n, m, g; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); add(i, a[i]); } int last = 0, l, r; while (m--) { scanf("%d", &g); if (g) { scanf("%d", &g); g ^= last; add(++n, g); } else { scanf("%d%d", &l, &r); l = (l ^ last) % n + 1; r = (r ^ last) % n + 1; if (l > r)swap(l, r); last = ask(l, r); printf("%d\n", last); } } } }

Ivan and Burgers

题意

长度位$n$的数组，$q$个询问，询问$(L,R)$的最大异或值

分析

同上题，记录最靠右的线性基，询问即可

代码

#include <iostream> #include <cstdio> #include <cstring> using namespace std; #pragma warning (disable:4996) const int maxn = 500005; int a[maxn], d[20], pos[20], v[maxn][20], p[maxn][20]; void add(int x, int value) { int t = x; for (int i = 19; i >= 0; i--) { if (value & (1 << i)) { if (!d[i]) { d[i] = value; pos[i] = x; break; } else if (pos[i] < x) { swap(d[i], value); swap(pos[i], x); } value ^= d[i]; } } for (int i = 0; i <= 19; i++) v[t][i] = d[i], p[t][i] = pos[i]; } int ask(int l, int r) { int res = 0; for (int i = 19; i >= 0; i--) if (p[r][i] >= l && (res ^ v[r][i]) > res) res ^= v[r][i]; return res; } int main() { int n, m; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); add(i, a[i]); } scanf("%d", &m); int l, r; while (m--) { scanf("%d%d", &l, &r); printf("%d\n", ask(l, r)); } }