Operation

1247 ワード

Operation
題意:0 l rはl,rの間で任意にいくつかの数を選択して異或値を最大にする.1 x末尾にx値を挿入します.
考え方:接頭辞の線形ベースを維持すればいい. 
#include
using namespace std;
const int N=1e6+5;
int n,q,c[N];
int pos[N][30],p[N][30];
void insert(int x,int num){
	for(int i=0;i<30;i++){
		pos[x][i]=pos[x-1][i];
		p[x][i]=p[x-1][i];
	}
	int tmp=num;
	int id=x;
	for(int i=29;i>=0;i--){
		if((tmp>>i)&1){
			if(!p[x][i]){
				p[x][i]=tmp;
				pos[x][i]=id;
				return;
			}
			if(pos[x][i]=0;i--)
		if(pos[r][i]>=l&&(res^p[r][i])>res)
			res^=p[r][i];
	return res;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&q);
		for(int i=0;i<30;i++)
			pos[0][i]=p[0][i]=0;
		for(int i=1,x;i<=n;i++){
			scanf("%d",&x);
			insert(i,x);
		}
		int last=0;
		int op,l,r,x;
		while(q--){
			scanf("%d",&op);
			if(op==0){
				scanf("%d%d",&l,&r);
				l=(l^last)%n+1;
				r=(r^last)%n+1;
				if(l>r)
					swap(l,r);
				printf("%d
",last=ask(l,r)); } else{ scanf("%d",&x); x^=last; insert(++n,x); } } } return 0; }