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,令val=x,pos=i。
从高到低考虑val的每一位,若当前位不为0:
考虑a[i]的这一位j:
(1)如果a[i][j]为0,插入val,且pos[i][j]=pos,插入结束。
(2)如果a[i][j]不为0
①、如果pos[i][j]<pos:
那么我们swap(a[i][j],val),swap(pos[i][j],pos),即我们让这一位的贡献让尽可能右边的数产生。
相当于现在插入的是交换后的val,pos,令val=val∧a[i][j],继续插入。
②、如果pos[i][j]>pos:令val=val∧a[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;
}