分析：如果能知道区间线性基，问题就解决了，所以一开始有个naive的想法，搞个线性基线段树，然而复杂度(32*nlogn)，果断T。。。
正解是预处理后缀线性基，并且每个基中的每一个分量位置尽量靠前，然后把k丢到左端点对应的线性基里跑，如果k最后不为0或者需要异或的位置超过了r，答案就是NO。
这样的后缀线性基可以从后面开始处理，插入x时，如果某一位已经有数且在数组中的位置在x之后，把x放入线性基替换掉这个数，然后用这个数接着跑。
1 #include2 #include 3 #include 4 #define SWAP(x, y)x ^= y, y ^=x, x ^= y; 5 using namespace std; 6 const int maxn = 5e5 + 5, inf = 1e9; 7 int n; 8 struct LinearBase{ 9 int a[32], n, loca[32];10 LinearBase(){11 memset(a, 0, sizeof(a));12 memset(loca, 0, sizeof(loca));13 n = 0;14 }15 void insert(int x, int k){16 int cur_loca = k;17 int d = 31;18 while(x && d >= 0){19 if(x & (1 << d)){20 if(a[d]){21 if(cur_loca < loca[d]){22 SWAP(loca[d], cur_loca);23 SWAP(a[d], x);24 }25 x ^= a[d];26 }else{27 loca[d] = cur_loca;28 a[d] = x;29 n++;30 break;31 }32 }33 d--;34 }35 }36 LinearBase operator = (LinearBase x){37 x.n = n;38 for(int i = 0; i < 32; i++)a[i] = x.a[i], loca[i] = x.loca[i];39 }40 int check(int k){41 int d = 31, r_min = 0;42 while(k && d>=0){43 if(k & (1 << d)){44 if(!a[d])return inf;45 r_min = max(r_min, loca[d]);46 k ^= a[d];47 }48 d--;49 }50 if(k)return inf;51 return r_min;52 }53 }lb[maxn];54 int read(){55 int ans = 0;56 char last = ' ', ch = getchar();57 while(ch >= '0' && ch <= '9')ans = ans * 10 + ch - '0', ch = getchar();58 return ans;59 }60 bool check(int l, int r, int k){61 LinearBase &b = lb[l];62 if(b.check(k) <= r)return true;63 return false;64 }65 int a[maxn];66 int main(){67 // freopen("e:\\in.txt","r",stdin);68 n = read();69 for(int i = 1; i <= n; i++)a[i] = read();70 lb[n].insert(a[n], n);71 for(int i = n - 1; i >= 0; i--){72 lb[i] = lb[i + 1];73 lb[i].insert(a[i], i);74 }75 int m,l,r,k;76 m = read();77 for(int i = 0; i < m; i++){78 l = read();r = read();k = read();79 if(check(l, r, k))puts("YES");80 else puts("NO");81 }82 return 0;83 }