题意:

初始时有n个数，现在有q次操作：

  • 查询[l,r]内选择一些数使得异或和最大；
  • 在末尾加入一个数。

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6579

题解：

这一道让我学习了线性基 学习传送门

这一道题 要我们强制 在线求线性基

用一个 val二维数组 标记右边界为i时对应的线性基

用一个 pos二维数组 标记当前该位插入的哪个数的位置

每次在末尾加入一个新的数，我们要让右边的数，尽量插到最高位中，所以要记录每次插入数的位置，方便更新

注意数组的大小， 我maxm宏定义的大小为32的时候就MLE了

AC_code:

 

/*
Algorithm:  在线线性基 
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define maxm 30
#define line printf("--------------");
using namespace std;
int a[maxn], val[maxn][maxm+3], pos[maxn][maxm+3];
int n, q, l, r, t, op, x, p;

void slove(int aa) {
	for(int j = maxm; j >= 0; j--) {
		val[aa][j] = val[aa-1][j];
		pos[aa][j] = pos[aa-1][j];
	}
	for(int j = maxm; j >= 0; j--) {// 求线性基
		if(x>>j&1) {
			if(!val[aa][j]) {
				val[aa][j] = x;
				pos[aa][j] = p;
				break;
			} else {
				if(pos[aa][j] < p) {
					swap(val[aa][j], x);
					swap(pos[aa][j], p);// 把最右边的尽量插入最高位
				}
				x ^= val[aa][j];
			}
		}
	}
}


int main() {
	scanf("%d", &t);
	while(t--) {
		int last = 0;
		memset(val,0,sizeof(val));
		memset(pos,0,sizeof(pos));
		scanf("%d %d", &n, &q);
		for(int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		for(int i = 1; i <= n; i++) {
			x = a[i];
			p = i;
			slove(i);
		}
		for(int i = 1; i <= q; i++) {
			scanf("%d", &op);
			if(op == 1) {
				scanf("%d", &x);
				x ^= last;
				a[++n] = x;
				p = n;
				slove(n);

			} else {
				scanf("%d %d", &l, &r);
				l = (l ^ last) % n + 1;
				r = (r ^ last) % n + 1;
				if(l > r) {
					swap(l, r);
				}
				int ans = 0;
				for(int j = maxm; j >= 0; j--) {
					if(pos[r][j] >= l && val[r][j]) {
						ans = max(ans, ans^val[r][j]);
					}
				}
				last = ans;
				printf("%d\n", ans);
			}
		}
	}
	return 0;
}