HDU–6579 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.

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=(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
1
3 3
0 1 2
0 1 1
1 3
0 3 4

Sample Output
1
3

题意:
给定一个序列a,有两种操作,查询 al- - -ar 中的数能异或出来的最大值;在序列后面加上一个数,使序列长度加一。

题解:
对所有 i∈(1,n) 维护一个 ( 1 , i ) 的线性基 a [ i ] [ 30 ] , 类似于前缀和的思想, 同时对每个线性基记录一下它每一位最后被插入的位置 pos [ i ] [ 30 ](于是线性基的insert函数就要稍微改一下), 这样在查询(L,R)区间的时候只有a[R]中pos大于等于L的位会对(L,R)区间有贡献。

怎么维护呢?
我们让对 当前 i 的高位产生贡献的数尽量的靠右。

a [ i ] a [ i ] = a [ i 1 ] x v a l = x p o s = i 假设我们现在维护 a [ i ] ,先令 a [ i ] = a [ i - 1 ] ,假设现在插入 x ,令val = x,pos = i。 a[i]a[i]=a[i1]xval=xpos=i

v a l 0 从高到低考虑 val 的每一位,若当前位不为0: val0
a [ i ] j 考虑 a [ i ] 的这一位 j : a[i]j
1 a [ i ] [ j ] 0 v a l p o s [ i ] [ j ] = p o s (1)如果 a [ i ] [ j ] 为0,插入val,且 pos [ i ] [ j ] = pos,插入结束。 1a[i][j]0valpos[i][j]=pos
2 a [ i ] [ j ] 0 (2)如果 a [ i ] [ j ] 不为0 2a[i][j]0
p o s [ i ] [ j ] < p o s : ①、如果 pos [ i ] [ j ] < pos: pos[i][j]<pos:
s w a p ( a [ i ] [ j ] , v a l ) , s w a p ( p o s [ i ] [ j ] , p o s ) 那么我们swap( a [ i ] [ j ] , val) , swap(pos[ i ] [ j ] , pos),即我们让这一位的贡献让尽可能右边的数产生。 swap(a[i][j],val),swap(pos[i][j],pos)
v a l p o s v a l = v a l a [ i ] [ j ] 相当于现在插入的是交换后的val,pos,令val=val \land a [ i ][ j ] ,继续插入。 valposval=vala[i][j]
p o s [ i ] [ j ] > p o s v a l = v a l a [ i ] [ j ] ②、如果 pos [ i ] [ j ] > pos:令val=val\land a [ i ][ j ] ,继续插入 pos[i][j]>posval=vala[i][j]

代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=1000100;
const int maxm=100100;
const int up=29;

struct node
{
    int p[30];
    int pos[30];
}a[maxn];

int n,m,cnt=0;

void _insert(int val)
{
    ++cnt;
    a[cnt]=a[cnt-1];
    int pos=cnt;
    for(int i=up;i>=0;i--)
    {
        if(val&(1<<i))
        {
            if(a[cnt].p[i]==0)
            {
                a[cnt].p[i]=val;
                a[cnt].pos[i]=pos;
                break;
            }
            else if(a[cnt].pos[i]<pos)
            {
                swap(a[cnt].p[i],val);
                swap(a[cnt].pos[i],pos);
            }
            val^=a[cnt].p[i];
        }
    }
}

int get_max(int l,int r)
{
    int ans=0;
    for(int i=up;i>=0;i--)
    {
        if(a[r].pos[i]<l) continue;
        if((ans^a[r].p[i])>ans) ans^=a[r].p[i];
    }
    return ans;
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        cnt=0;
        int last=0;
        int op,x,y;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&x),_insert(x);
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&op);
            if(op==0)
            {
                scanf("%d%d",&x,&y);
                x=(x^last)%cnt+1,y=(y^last)%cnt+1;
                if(x>y)swap(x,y);
                printf("%d\n",last=get_max(x,y));
            }
            else
            {
                scanf("%d",&x);
                _insert(x^last);
            }
        }
    }
    return 0;
}