Hang Technology Multi-Biography First -B-Operation - Electricity, First, hang, Multi-school, one, operation

Title description

There is an integer sequence a of length n and there are two kinds of operations:
0 lr: 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 means the answer to the last type 0 operation and is initially zero:
For every type 0 operation, let l=(l xor lastans)mod n + 1, r=(r xor lastans)mod n + 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

Sample output

1
3

Question meaning:

The largest XOR sum of the query interval [l,r]. 


Official solution:

The violent approach can use the data structure to maintain the interval linear basis, but it will definitely not pass.

Maintain the prefix linear basis (upper triangular state) of the sequence greedily, and for each linear basis, put the number that appears to the right as high as possible 
That is to say, when inserting a new number, it is necessary to record the position of the number in the corresponding position at the same time, and when the position that can be inserted is found, if the new number is more to the right than the original number in the position, the The original number in the position is pushed to the lower position.

When seeking the maximum value, traverse from high to low. If the number in this digit appears at the left end of the interval in the query On the right side and the answer can be made larger, it is XORed into the answer. 
For each bit of the linear base, the number in the higher position of the linear base XORed with it must appear on the right side of it (otherwise it will be inserted at that position), so the correctness of the approach Obviously.

Linear basis:
https://blog.csdn.net/a_forever_dream/article /details/83654397
https://blog.sengxian.com/algorithms/linear-basis?tdsourcetag=s_pctim_aiomsg

#include 

#define ll long long

using namespace std;

const int N=5e5+10;

int T,n,m;

int p[N][31],pos [N][31];

void add(int val,int x)

{

 for (int i=0;i<=30;i++) p[x][i]=p[x-1][i],pos[x][i]=pos[x-1< span style="color: #000000;">][i];

 int now=x;

 for (int i=30;i>=0;i--)

 if (val&(1<<i))

 {

 if (!p[x][i])

 {

 p[x][i]=val;

 pos[x][i]=now;

 break;

}

 if (pos[x][i]<now) swap( p[x][i],val),swap(pos[x][i],now);

 val^=p[x][i];

}

}

int query(int l,int r)

{

 int ret=0;

 for (int j=30;j>=0;j--)

 if (pos[r][j]>=l && (ret^p[r][j])>ret ) ret^=p[r][j];

 return ret;

}

int main()

{

 // freopen("1.in","r", stdin);

 // freopen("1.out","w", stdout);

 scanf("%d",&T);

 while (T--)

 {

 scanf("%d%d",&n,&m);

 int op,x,l,r;

 for (int i=1;i<=n;i++)

 {

 scanf("%d",&x);

 add(x,i);

}

 int lastans=0;

 while (m--)

 {

 scanf("%d",&op);

 if (op==0)

 {

 scanf("%d%d",&l,&r);

 l=(l^lastans)%n+1;

 r=(r^lastans)%n+1;

 if (l>r) swap(l,r);

 lastans=query(l,r);

 printf("%d
",lastans);

}

 else

 {

 scanf("%d",&x);

 x^=lastans;

 n++;

 add(x,n);

}

}

}

 // fclose(stdin);

 // fclose(stdout);

 return 0 ;

}

View Code

There is an integer sequence a of length n and there are two kinds of operations:
0 lr: 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.

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=(l xor lastans)mod n + 1, r=(r xor lastans)mod n + 1, and then swap(l, r) if l>r .
For every type 1 operation, let x=x xor lastans.