杭电多校第一场-B-Operation

题目描述

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.

输入

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.

输出

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

样例输入

1
3 3
0 1 2
0 1 1
1 3
0 3 4

样例输出

1
3

题意：
查询区间[l,r]的最大异或和。

官方题解：
暴力的做法可以用数据结构维护区间线性基，但肯定过不了。

贪心地维护序列的前缀线性基 (上三角形态)，对于每个线性基，将出现位置靠右的数字尽可能地放在高位
也就是说在插入新数字的时候，要同时记录对应位置上数字的出现位置，并且在找到可以插入的位置的时候，如果新数字比位置上原来的数字更靠右，就将该位置上原来的数字向低位推。

在求最大值的时候，从高位向低位遍历，如果该位上的数字出现在询问中区间左端点的右侧且可以使答案变大，就异或到答案里。
对于线性基的每一位，与它异或过的线性基更高位置上的数字肯定都出现在它右侧 (否则它就会被插入在那个位置了)，因此做法的正确性显然。

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

#include <bits/stdc++.h>
#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][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\n",lastans);
            }
            else
            {
                scanf("%d",&x);
                x^=lastans;
                n++;
                add(x,n);
            }
        }
    }
   // fclose(stdin);
   // fclose(stdout);
    return 0;
}

View Code