思路真的是挺巧妙的。
让我惊叹，原来线性基还能这么做？！？！
好吧，这种取若干个数异或凑数的题目怎么能少的了线性基呢？
但是，问题集中在于怎么快速提取一个区间的线性基
暴力n^2
线段树维护线性基？分区间logn，合并一次logn^2 O（nlogn^3）GG
然后就一脸不可做了。
题解：
“容易”想到，一个线性基里面的元素可以用线性基外的元素替换的。
只要保证还能表示出原来的线性空间，那么一定可以替换。
所以，我们给每个点维护一个线性基。
lb[r]表示，由1~r的所有元素选择构成的线性基，其中元素尽可能地靠后。
当lb[r-1]转移到lb[r]的时候，
可以把r-1的所有元素拿出来，把a[r]拿出来，按照位置排序，贪心加入lb[r]。
这样，预处理O(nlogn^2)
查询呢？直接把lb[r]中的元素拿出来，根据位置是否大于等于l放进一个临时线性基里。
之后把k尝试加入线性基，能加入就说明无法表出，否则可以。
O(nlogn^2)
但是还是过不去？！~？！？
发现，我们转移lb，查询的时候，真的是非常暴力的操作。
能不能再少一个log？
发现，lb[r-1]->lb[r]不就是可能多了一个a[r]吗？
所以有一个贪心策略：
首先复制过来lb[r-1],尝试加入x=a[r]
如果x有j位的1，lb中没有，加进去，break。
如果lb中有，如果lb的j这个位置的元素实际位置更靠前，那么可能询问的时候取不到，就和x换一下，然后继续放下一位（记得无论如何要异或一下）。
并且发现，我们这样做，会使得高位的位置尽可能靠后。
所以询问的时候，从高位到低位，如果没有这一位，那么直接NO就可以了。
如果一直可以，那么就是YES
Code：
#include<bits/stdc++.h> #define numb ch-'0' #define ri register int #define il inline using namespace std; const int N=500000+10; const int M=32; int n,m; int a[N]; char ch; il void rd(int &x){ x=0; while(!isdigit(ch=getchar())); for(x=numb;isdigit(ch=getchar());x=x*10+numb); } struct node{ int lin[M]; int pos[M]; }lb[N]; int main() { rd(n); for(ri i=1;i<=n;i++){ rd(a[i]); } for(ri i=1;i<=n;i++){ lb[i]=lb[i-1]; int tmp=a[i]; int po=i; for(ri j=29;j>=0;j--){ if(tmp&(1<<j)){ if(lb[i].lin[j]==0){ lb[i].lin[j]=tmp; lb[i].pos[j]=po; break; } else { if(po>lb[i].pos[j]) { swap(tmp,lb[i].lin[j]); swap(po,lb[i].pos[j]); } tmp^=lb[i].lin[j]; } } } } rd(m); int l,r,k; for(ri i=1;i<=m;i++){ rd(l),rd(r),rd(k); bool fl=true; for(ri j=29;j>=0;j--){ if(k&(1<<j)){ if(lb[r].lin[j]==0){ fl=false;break; } else{ if(lb[r].pos[j]<l){ fl=false;break; } else{ k^=lb[r].lin[j]; } } } } if(fl){ puts("YES"); } else puts("NO"); } return 0; }
upda：2016.6.10
其实就是一个套路，维护最晚时间线性基
只要证明两个事：
1.合法的区间一定合法，不合法的区间一定还是不合法
2.线性基里可以取的元素一定是[L,R]元素暴力加入后的线性基（相当于可以代替暴力插入[L,R]的元素）
先证明2
设R的最晚线性基为B，把[L,R]元素暴力插入的线性基是S
发现可以取的元素，如果形如a^b^c^d（不妨认为，出现时间a<b<c<d）那么如果这个元素可以保留，那么b,c,d有关的都可以保留，
所以一定是S的子集
又如果是真子集，即存在一个元素属于S，却不属于B，那么这个元素，一定可以顶替掉B中<L的一个元素，与最晚时间线性基矛盾
由于2成立，1自然就成立了。