(2022 Hangdian multi school III) 1011 link is as bear (thinking + linear basis)

Topic link ： Hangzhou Electric Power Co., Ltd 4 - Virtual Judge

subject ：

The sample input ：

2
5
10 10 10 10 10
4
1 1 2 1

Sample output ：

10
3

The question ： Multiple sets of samples , Each group of examples gives one n, Represents the number of elements in the array , The next line shows n Number , We can operate it , Select an interval for each operation [l,r], After operation, it will be located in [l,r] All of the numbers become a[l]^a[l+1]^……^a[r], Finally, we need to change the whole array into the same value , Ask what is the maximum value we can get ？ At the start of the n The number guarantees that two numbers are the same .

analysis ： The conclusion of this question is From here n Select any number from the number and XOR , The maximum value that can be obtained is the answer .

prove ： If we have n Number a[1~n], among a[p1],a[p2],……,a[pk]k The XOR value of the number is the largest , Then we have to prove that our final answer can be a[p1]^a[p2]^……^a[pk], hypothesis p1<p2<……<pk

First, consider the interval [p1,p2] All the numbers inside become a[p1]^p[p2]

If p2=p1+1, Then the two can be directly exclusive or

If p2>p1+2, in other words p1 and p2 There are at least two numbers between , Then we can operate the interval [p1+1,p2-1] However, all of them become 0, For example, if the interval has even numbers , Then we can XOR adjacent to each other , Then every two adjacent numbers become the same number , Do the same operation again , Then all the numbers in this interval will become 0, Finally, the interval [p1,p2] The purpose can be achieved by exclusive or of all the numbers in . If there are odd numbers between them , Take three numbers as an example ,x,y,z, First, let x,y XOR twice becomes 0, And then give up z The next one 0 and z XOR two times , You can turn all three into 0, After the operation, you can also change all the numbers in the interval to 0.

The last situation is p1 and p2 There is only one number between , This is why there must be two numbers in the title that are the same . In this case, we can't deal with p and p Merge the numbers between , Suppose two identical numbers are x, Then let's merge and leave first x The two closest pi and pi+1, Let's assume that p1 On the left . The extreme case is （o Represents any number ）

x,p1,o,p2,o,x This situation

We will first x and p1 Conjunction, exclusion or get y,y,o,p2,o,x(y=x^p1)

And then the second position and the third position are all changed into 0 obtain ：y,0,0,p2,o,x(y=x^p1)

XOR the first four positions again to get ：z,z,z,z,o,x(z=x^p1^p2)

Then change the fourth position and the fifth position into two consecutive XORs 0 obtain ：z,z,z,0,0,x

Then XOR the last four positions to get z,z,p1^p2,p1^p2,p1^p2,p1^p2

Finally, XOR the first two positions to 0 And XOR the first three to get p1^p2,p1^p2,p1^p2,p1^p2,p1^p2,p1^p2

Through this method introduced above, you can get any desired XOR value from the entire array

The rest is to find an XOR maximum , This is the operation of linear basis , Just put on the template directly

Linear basis is used to find difference or maximum , Minimum value and k High value

Here is the code ：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
struct L_B
{
    const static int BASE = 63;
    long long d[BASE], p[BASE];
    int cnt, flag;
    void init()
    {
        memset(d, 0, sizeof(d));
        memset(p, 0, sizeof(p));
        cnt = 0;
        flag = 0;
    } // 1e18 The number within is applicable .
    inline bool insert(long long val)
    {
        for (int i=BASE- 1; i >= 0; i--)
        {
            if (val & (1ll << i))
            {
                if (!d[i])
                {
                    d[i] = val;
                    return true;
                }
                val ^= d[i];
            }
        }
        flag = 1; // You can XOR out 0
        return false;
        //  To judge val Whether it exists in the linear basis .
    }
    long long query_max()
    {
        long long res = 0;
        for (int i = BASE - 1; i >= 0; i--)
        {
            if ((res ^ d[i]) > res)
                res ^= d[i];
        }
        return res;
    }
    long long query_min()
    { //  It should be judged in advance whether it is 0 The situation of ..QAQ
        if (flag)
            return 0;
        for (int i = 0; i <= BASE - 1; i++)
        {
            if (d[i])
                return d[i];
        }
    }
    void rebuild()
    { //  Used to find the number k Small value . Independent pretreatment is required first 
        for (int i = BASE - 1; i >= 0; i--)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (d[i] & (1ll << j))
                    d[i] ^= d[j];
            }
        }
        for (int i = 0; i <= BASE - 1; i++)
        {
            if (d[i])
                p[cnt++] = d[i];
        }
    }
    long long kthquery(long long k)
    {             //  Pay attention to judge whether the original sequence is exclusive or out 0 The situation of ,  At this point, we should put k --  In the following operations .
        if (flag) // sentence 0
            --k;
        if (!k)
            return 0;
        long long res = 0;
        if (k >= (1ll << cnt))
            return -1;
        for (int i = BASE - 1; i >= 0; i--)
        {
            if (k & (1LL << i))
                res ^= p[i];
        }
        return res;
    }
    void Merge(const L_B &b)
    { //  hold b This linear base is inserted into the current linear base .
        for (int i = BASE - 1; i >= 0; i--)
            if (b.d[i])
                insert(b.d[i]);
    }
} LB;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		L_B p;
		p.init();
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			long long t;
			scanf("%lld",&t);
			p.insert(t);
		}
		printf("%lld\n",p.query_max());
	}
	return 0;
}