从左到右一共n个数,数字下标从1到n编号。
一共m次询问,每次询问是否能从第L个到第R个数中(包括第L个和第R个数)选出一些数使得他们异或为K。
数据量比较大。
输入请用挂
输出请用puts
Input
单组测试数据。 第一行一个整数n(0<n<=500,000)。 第二行n个整数,0<每个数<2^30。 第三行一个数m,表示询问次数(0<m<=500,000)。 接下来m行每行三个数,L,R,K(0<L<=R<=n,0<K<2^30)。
Output
M行,每行为YES或NO
Input示例
5 1 1 2 4 6 3 1 2 1 2 4 8 3 5 7
Output示例
YES NO NO
线性基~
如果只有一个固定区间,我们只需要求出线性基再贪心地异或即可得出答案。
所以关键即在于怎样求出区间内的线性基。有一种神奇的方法(不知道为什么,网上学的):我们以f[i]表示[i,n]的线性基,那么f[i]可以由f[i+1]推得,只要处理a[i]即可。我们把a[i]不断与已有线性基比较,如果当前没有这种线性基,就记录下来;如果已有,就保留编号较小的一个。
最后不断贪心地把k与f[l](要求标号<=r)异或,当最后k==0时,就是YES。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;int n,t,a[500001],l,r,k;struct node{int x,id;
}f[500002][30],tmp;int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}int main()
{n=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=n;i;i--){memcpy(f[i],f[i+1],sizeof(f[i+1]));tmp=(node){a[i],i};for(int j=29;~j;j--)if(tmp.x&(1<<j)){if(!f[i][j].x) swap(tmp,f[i][j]);else{if(f[i][j].id>tmp.id) swap(tmp,f[i][j]);tmp.x^=f[i][j].x;}}}t=read();while(t--){l=read();r=read();k=read();for(int i=29;~i;i--)if(k&(1<<i)){if(f[l][i].id>r) continue;k^=f[l][i].x;}if(!k) puts("YES");else puts("NO");}return 0;
}