hdu6579

发表于 分类于 ， ， 阅读次数： 7 本文字数： 2.3k 阅读时长 ≈ 2 分钟

###name Operation

###descirption There is an integer sequence a of length n and there are two kinds of operations: 0 l r: select some numbers from al...ar so that their xor sum is maximum, and print the maximum value.

1 x: append x to the end of the sequence and let n=n+1.

###input There are multiple test cases. The first line of input contains an integer T(T≤10), indicating the number of test cases. For each test case: The first line contains two integers n,m(1≤n≤5×105,1≤m≤5×105), the number of integers initially in the sequence and the number of operations. The second line contains n integers a1,a2,...,an(0≤ai<230), denoting the initial sequence. Each of the next m lines contains one of the operations given above. It's guaranteed that ∑n≤106,∑m≤106,0≤x<230. And operations will be encrypted. You need to decode the operations as follows, where lastans denotes the answer to the last type 0 operation and is initially zero: For every type 0 operation, let l=(lxorlastans)modn+1, r=(rxorlastans)modn+1, and then swap(l, r) if l>r. For every type 1 operation, let x=x xor lastans.

###output For each type 0 operation, please output the maximum xor sum in a single line.

###sample input 1 3 3 0 1 2 0 1 1 1 3 0 3 4

###sample output 1 3

###toturial 我们使用线性基，对每一个前缀都建立一个线性基，贪心的选择考后的向量作为基即可，如此则查询T(30)，添加值T(30)，关键点在于如何通过一个前缀构建另一个前缀的线形基，我们只要保证线形基中的元素有顺序，即某个前缀的基都是相对于这个前缀的后缀最简形式，那么我们就可以在后面进行换基，来构建另一个前缀的基

###code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;

#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)

const int maxn=1e6+6;
int bs[maxn][30],ps[maxn][30];
void add(int n,int x){
    rep(i,0,29) bs[n][i]=bs[n-1][i],ps[n][i]=ps[n-1][i];
    int pos=n;
    per(i,29,0) if(1<<i&x) {
        if(bs[n][i]==0) {
            bs[n][i]=x,ps[n][i]=pos;
            break;
        }
        else {
            if(ps[n][i]<pos)swap(bs[n][i],x),swap(ps[n][i],pos);
            x^=bs[n][i];
        }
    }
}
inline int read(){int x;scanf("%d",&x);return x;}
int main() {
    int t=read();
    while(t--){
        int n=read(),m=read();
        rep(i,1,n) add(i,read());
        int lst=0;
        while(m--){
            if(read()==1) add(++n,read()^lst);
            else{
                int l=(read()^lst)%n+1,r=(read()^lst)%n+1;
                if(l>r)swap(l,r);
                lst=0;
                per(i,29,0) if(ps[r][i]>=l) lst=max(lst,lst^bs[r][i]);
                printf("%d\n",lst);
            }
        }
    }
}