hdu6579 线性基

题目链接hdu6579
题目就是给你你个序列，问你任意区间内去取数，要求这些数的异或和最大，还要求可以增加这个序列。
从序列里面取数求异或和最大，这个是线性基模板题，但是题目要求的不一样，要的是任意区间。要怎么处理呢？就是我们开一个二维的线性基，f[i][j], i表示的是f[i]这一维的线性基是[1,i]的。
但是这只是解决了右端点，但是左端点怎么办？那么其实就是对于[1,i]这个区间的线性基的数目是固定的，但是数的组合可以有很多种，所以我们在插入线性基的时候，线性基同一个位置的数，如果这个数的位置比当前这个数的位置要小，则交换。就是这个位置的线性基替换成位置比较大的数就可以了。最后得答案只要再加一个判断算这个线性基的位置是不是在询问的区间内即可。

#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const long long max_ = 1e6 + 100;
inline int read()
{
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
int n, m;
int node[max_][32], f[max_][32];
void add_(int x, int i) {
	int k = i;
	int  temp;
	for (int j = 30; j >= 0; j--)f[i][j] = f[i - 1][j], node[i][j] = node[i - 1][j];
	for (int j = 30; j >= 0; j--) 
		if (x >> j) {
			if (!f[i][j]) {
				f[i][j] = x;
				node[i][j] = k;
				break;
			}
			else {
				if (k > node[i][j]) {
					temp = k; k = node[i][j]; node[i][j] = temp;
					temp = x; x = f[i][j]; f[i][j] = temp;
				}
				x ^= f[i][j];
			}

		}
	
}
int main() {
	int T ;
	scanf("%d", &T);
	while (T--) {
		memset(node, 0, sizeof(node));
		memset(f, 0, sizeof(f));
		n, m ;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++) {
			int t;
			scanf("%d", &t);
			add_(t, i);
		}
		int lastans = 0;
		while (m--) {
			int a,b,c,d;
			scanf("%d", &a);
			if (a == 0) {
				
				scanf("%d%d", &b,&c);
				b = (b ^ lastans) % n + 1;
				c = (c ^ lastans) % n + 1;
				if (b > c) swap(b, c);
				int ans = 0;
				for (int i = 30; i >= 0; i--) {
					if ((ans^f[c][i]) > ans&&node[c][i] >= b) {
						ans ^= f[c][i];
					}
						
				}
				printf("%d\n", ans);
				lastans = ans;
			}
			else {

				scanf("%d", &d);
				d ^= lastans;
				n++;
				add_(d, n);
			}
		}

	}
	return 0;
}