夏晓光(loveJY)的博客

静态区间线性基

考虑chz菜者的做法:离线扫描线,然后从1~n维护一个后缀线性基,每次插入一个数$x_i$,就暴力从i到1全部更新一遍,更新不动了就停止,可以证明此复杂度均摊$O(n*64^2)$,荣获0pts的好成绩!

然后您发现我们复杂度主要在于插入时的更新,如果我们只更新1次就能起到n次的效果就好了...

于是我们有一个贪心的想法,$pos[i][j]$表示前i个数第j个基最靠右的位置,然后我们对于插入x的过程,可以贪心的只找最靠右的位置进行更新....

其实这个思想并不巧妙,早在区间数字种类的时候就用到过这样的扫描线贪心,但是对于线性基不太会所以没做出来QAQ

然后您发现有点细节,就是pos的更新,想想就好了,我们其实是在多个线性基上横跳的过程

所以一次可能会更新多个pos?不过没关系,因为我们但凡要更新新的值就一定要^上之前某个基,那么我们之后的就相当于只能更新之前某个基之后的某个基了!

其实看看代码就好

code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 5e5 + 7;
int n, Q;
int a[MAXN];
int bsc[MAXN][22], lst[MAXN][22];

int main() {
	scanf("%d", &n);
	for(int i = 1, t, npos; i <= n; ++i) {
		scanf("%d", &a[i]);
		for(int k = 0; k <= 21; ++k)bsc[i][k] = bsc[i - 1][k], lst[i][k] = lst[i - 1][k];
		t = a[i];
		npos = i;
		for(int k = 21; k >= 0; --k) {
			if(!(t >> k) & 1)continue;
			if(!bsc[i][k]) {
				bsc[i][k] = t;
				lst[i][k] = npos;
				break;
			}
			if(lst[i][k] < npos) {
				swap(t, bsc[i][k]);
				swap(lst[i][k], npos);
			}
			t ^= bsc[i][k];
		}
	}
	scanf("%d", &Q);
	for(int i = 1, x, y; i <= Q; ++i) {
		scanf("%d%d", &x, &y);
		int ans = 0;
		for(int k = 21; k >= 0; --k) {
			// printf("%d %d %d %d\n", bsc[y][k], lst[y][k], ans ^ bsc[y][k], ans);
			if(lst[y][k] >= x && (ans ^ bsc[y][k]) > ans)
				ans ^= bsc[y][k];
		}
		printf("%d\n", ans);
	}
	return 0;
}