2017 ICPC西安区域赛 A - XOR (线段树并线性基)

时间:2021-05-27 15:42:41

链接:https://nanti.jisuanke.com/t/A1607

题面:

 

Consider an array AA with n elements . Each of its element is A[i]A[i] (1 \le i \le n)(1≤i≤n) . Then gives two integers QQ, KK, and QQ queries follow . Each query , give you LL, RR, you can get ZZ by the following rules.

To get ZZ , at first you need to choose some elements from A[L]A[L] to A[R]A[R] ,we call them A[i_1],A[i_2]…A[i_t]A[i1​],A[i2​]…A[it​] , Then you can get number Z = KZ=K or (A[i_1]A[i1​] xor A[i_2]A[i2​] … xor A[i_t]A[it​]) .

Please calculate the maximum ZZ for each query .

Input

Several test cases .

First line an integer TT (1 \le T \le 10)(1≤T≤10) . Indicates the number of test cases.Then TT test cases follows . Each test case begins with three integer NN, QQ, KK (1 \le N \le 10000,\ 1 \le Q \le 100000 , \ 0 \le K \le 100000)(1≤N≤10000, 1≤Q≤100000, 0≤K≤100000) . The next line has NN integers indicate A[1]A[1] to A[N]A[N] (0 \le A[i] \le 10^8)(0≤A[i]≤108). Then QQ lines , each line two integer LL, RR (1 \le L \le R \le N)(1≤L≤R≤N) .

Output

For each query , print the answer in a single line.

样例输入复制

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

样例输出复制

3
7
7

题目来源

ACM-ICPC 2017 Asia Xi'an

跟树套树差不多,线段树每个节点建个线性基,写个合并函数,对k取反,每个数对取反后的k取且,就可以转化成线性基中取与k异或最大值了

实现代码:

#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid int m = (l + r) >> 1
const int M = 1e4+;
int a[M];
struct L_B{
int b[],nb[],tot;
void init(){
memset(b,,sizeof(b));
} bool Insert(int x){
for(int i = ;i >= ;i --){
if(x&(<<i)){
if(!b[i]){
b[i] = x;
break;
}
x ^= b[i];
}
}
return x > ;
} int Max(int x){
int ret = x;
for(int i = ;i >= ;i --)
ret = max(ret,ret^b[i]);
return ret;
} int Min(int x){
int ret = x;
for(int i = ;i <= ;i ++)
if(b[i]) ret ^= b[i];
return ret;
} void rebuild(){
for(int i = ;i >= ;i --)
for(int j = i-;j >= ;j --)
if(b[i]&(<<j)) b[i]^=b[j];
for(int i = ;i <= ;i ++)
if(b[i]) nb[tot++] = b[i];
} int K_Min(int k){
int res = ;
if(k >= (<<tot))
return -;
for(int i = ;i >= ;i --)
if(k&(<<i))
res ^= nb[i];
return res;
} L_B merge(L_B v){
L_B ret;
for(int i = ;i <= ;i ++) ret.b[i] = b[i];
for(int i = ;i <= ;i ++){
for(int j = i;j >= ;j --){
if(v.b[i]&(<<j)){
if(ret.b[j]) v.b[i] ^= ret.b[j];
else {
ret.b[j] = v.b[i]; break;
}
}
}
}
return ret;
}
}t[M<<]; void build(int l,int r,int rt){
if(l == r){
t[rt].init();
t[rt].Insert(a[l]);
return ;
}
mid;
build(lson); build(rson);
t[rt] = t[rt<<].merge(t[rt<<|]);
} L_B query(int L,int R,int l,int r,int rt){
if(L <= l&&R >= r){
return t[rt];
}
mid;
if(L <= m&&m < R) return query(L,R,lson).merge(query(L,R,rson));
if(L <= m) return query(L,R,lson);
if(R > m) return query(L,R,rson);
} int main()
{
int T,n,q,k,l,r;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&q,&k);
k = ~k;
for(int i = ;i <= n;i ++)
scanf("%d",&a[i]),a[i]&=k;
k = ~k;
build(,n,);
for(int i = ;i <= q;i ++){
scanf("%d%d",&l,&r);
L_B ans = query(l,r,,n,);
int an = ans.Max(k);
printf("%d\n",an);
}
}
return ;
}