【2017西安】 XOR (线性基+思维）

亦凉 2021-11-09 11:42 308阅读 0赞

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][ACM-ICPC 2017 Asia Xi_an]

**SOLUTION:**

离线维护区间的线性基，对于某一个求答案时因为还要并上k，也就是说，k的2进制位一的位置时不需要考虑的

因此我们拿到一个区间的线性基后，在k的2进制位是0的位置所能异或出来的最大值，也就是抹掉之后，在建立

一个线性基

**CODE:**

#include<bits/stdc++.h> #define inf 0x3f3f3f3f #define sc(x) scanf("%d",&(x)) #define ls now<<1 #define rs now<<1|1 #define lson l,mid,ls #define rson mid+1,r,rs using namespace std; int n,q,k; const int N = 100010; int a[N]; int pos[40]; int lb[40]; int tmp[40]; int lb2[40]; struct aa { int l,r; int id; bool operator<(const aa b)const { if(r==b.r)return l<=b.l; return r<b.r; } }f[N]; #define ll long long inline void inser2(int v) { for(int i=30;i>=0;i--) { if(!((v>>i)&1))continue; if(!lb2[i]) { lb2[i]=v; break; } v^=lb2[i]; } } inline void inser(int v,int p) { for(int i=30;i>=0;i--) { if(!((v>>i)&1))continue; if(!lb[i]) { pos[i]=p; lb[i]=v; break; } if(pos[i]<p) { swap(pos[i],p); swap(lb[i],v); } v^=lb[i]; } } int all=(1<<30)-1; int ans[N]; inline int get(int l) { int cnt=0; for(int i=30;i>=0;i--) { /// if(pos[i]>=l&& (k|(t^lb[i])) > (k|t)) t^=lb[i]; if(pos[i]>=l)tmp[i]=lb[i]; } int cc=(all^k); int t=0; for(int i=30;i>=0;i--)tmp[i] &= cc; for(int i=30;i>=0;i--)inser2(tmp[i]); for(int i=30;i>=0;i--) { if((k|(t^lb2[i])) > (k|t)) t^=lb2[i]; } for(int i=0;i<=30;i++)tmp[i]=0,lb2[i]=0; return t|k; } int main() { int t; sc(t); while(t--) { sc(n); sc(q); sc(k); for(int i=1;i<=n;i++)sc(a[i]); for(int i=1;i<=q;i++) { sc(f[i].l); sc(f[i].r); f[i].id=i; } sort(f+1,f+1+q); int now=1; for(int i=1;i<=q;i++) { while(now<=f[i].r)inser(a[now],now),now++; ans[f[i].id] = k|(get(f[i].l)); // cout<<now<<endl; // cout<<f[i].id<<" "<<ans[f[i].id]<<endl; } for(int i=1;i<=q;i++)cout<<ans[i]<<endl; for(int i=1;i<=n;i++)ans[i]=0; for(int i=30;i>=0;i--)lb[i]=0,pos[i]=0; } return 0; }

转载于:https://www.cnblogs.com/zhangbuang/p/11258225.html

[ACM-ICPC 2017 Asia Xi_an]: https://nanti.jisuanke.com/acm?kw=ACM-ICPC%202017%20Asia%20Xi%27an