【2019 Multi-University 1 B】Operation 题解

题目大意

  有一个长度为 $n$ 的序列 $a_1\cdots a_n$，有 $m$ 个操作，操作有两种：
  $0~l~r$：选择 $a_l\cdots a_r$ 的一个子序列，使得其异或和最大，求该异或和；
  $1~x$：a[++n]=x;
  强制在线。

  数据组数 $T \leq 10$，时限 4s
  $n,m \leq 5\times 10^5,\ \ (\sum n),(\sum m) \leq 10^6,\ \ 0 \leq x,a_i \leq 2^{30}$

题解

  吹爆优秀的队友想出了优秀的 $O(n \log a_i)$ 做法！

  子序列最大异或和肯定是线性基了，直接线段树维护区间线性基有 3 个 $\log$ 就会 T 掉。

  于是考虑每个点 $i$ 维护 $1$~$i$ 的线性基。对于点 $i$，首先它要继承 $i-1$ 的线性基，然后把 $a_i$ 加进去，但不是普通的加，而是更新式地加。假设 $a_i$ 的最高位是 $w$，若线性基里 $w$ 这个位为空，则直接加进去；若这个位放了一个数 $y_w$，并且它比较旧（在原序列中的下标比 $i$ 小），则把 $y_w$ 替换成 $a_i$，然后 $y_w$ 当作一个新来的数继续插入线性基。
  这样一来，相当于我所用的基元都是最新的，最靠近 $i$ 的。
  那么询问 $[l,r]$ 的时候，就看 $r$ 的线性基，先把 $l$ 之前的基元去掉，然后剩下的基元求最大异或和就行了。

  这样的时间就是 $O(n \log a_i)$ 的了。

代码

//来自队友

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cstring>
#define cint const int &
using namespace std;
typedef long long ll;
#define rep(i,l,r) for (int i=l;i<=r;i++) 
int n,m,tt,a[1005000],pos[1005000][32],val[1005000][32];
void insert(int x,int xval){
	rep(i,0,30) {
		pos[x][i]=pos[x-1][i];
		val[x][i]=val[x-1][i];
	}
	int tmp=x;
	for (int i=30;i>=0;i--) if (xval&(1<<i)){
		if (!val[x][i]) {
			pos[x][i]=tmp;
			val[x][i]=xval;
			break;
		}
		else {
			if (pos[x][i]<tmp){
				swap(pos[x][i],tmp);
				swap(val[x][i],xval);
			}
			xval^=val[x][i];
		}
	}
}
int main() {
//	freopen("in.txt","r",stdin);
	scanf("%d",&tt);
	while (tt--){
		scanf("%d%d",&n,&m);
		rep(i,1,n) {
			scanf("%d",&a[i]);
			insert(i,a[i]);
		}
		int ans=0;
		rep(i,1,m){
			int op;
			scanf("%d",&op);
			if (op==1){
				int x; scanf("%d",&x);
				x^=ans;
				++n;
				insert(n,x);
			}
			else {
				int l,r; scanf("%d%d",&l,&r);
				l=(l^ans)%n+1; r=(r^ans)%n+1;
				if (l>r) swap(l,r);
				ans=0;
				for (int j=30;j>=0;j--){
					if (pos[r][j]>=l&&val[r][j]) ans=max(ans,ans^val[r][j]);
				}
				printf("%d\n",ans);
			}
		}
		rep(i,0,n) rep(j,0,30) val[i][j]=pos[i][j]=0;
	}
}