思路:
- 问xor起来有没有某个值, 想到线性基
- 然后发现问L-R区间的集合都要表示x, 利用线性基的交集解决
- 在利用线段树解决区间问题
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <iostream> using namespace std; typedef unsigned int ui; const int maxn = 50005; struct L_B{ //线性基结构体 ui b[35]; bool zero; //判断能否异或出0 void init(){ zero = false; for(int i = 0; i <= 31; i++) b[i] = 0; } }; struct Node{ L_B node; int l; int r; }; Node tree[maxn << 2]; int n, m; bool Insert(L_B &A, ui t){ //将t尝试插入线性基A,注意这里如果能插入返回false,否则返回true(这样写是为这道题改造的,一般情况是能插入返回true) if(t == 0){ if(A.zero) return true; else return false; } for(int i = 31; i >= 0; i--){ if(t & (1u << i)){ if(A.b[i]){ t ^= A.b[i]; }else{ A.b[i] = t; return false; } } } A.zero = true; return true; } L_B Merge(L_B A, L_B B){ //求线性基A与线性基B的交集。 L_B C, ALL; C.init(), ALL.init(); ui cnt[35]; for(int i = 0; i <= 31; i++){ C.b[i] = A.b[i]; cnt[i] = (1u << i); } for(int i = 31; i >= 0; i--){ ui v = B.b[i]; if(v){ ui temp = 0; bool can = true; for(int j = 31; j >= 0; j--){ if(v & (1u << j)){ if(C.b[j]){ v ^= C.b[j]; temp ^= cnt[j]; }else{ can = false; C.b[j] = v; cnt[j] = temp; break; } } } if(can){ ui k = 0; for(int j = 31; j >= 0; j--){ if(temp & (1u << j)){ k ^= C.b[j]; } } Insert(ALL, k); } } } return ALL; } void build(int k, int l, int r){ //建树 tree[k].l = l; tree[k].r = r; if(l == r){ //建立叶子节点 int cnt; scanf("%d", &cnt); tree[k].node.init(); for(int i = 1; i <= cnt; i++){ ui t; scanf("%u", &t); Insert(tree[k].node, t); //往此叶子节点插入对应集合的值。 } return; } int mid = (l + r) >> 1; build(2*k, l, mid); build(2*k+1, mid+1, r); tree[k].node = Merge(tree[2*k].node, tree[2*k+1].node); //回溯就求左右子节点线性基的交集 return; } bool query(int k, int l, int r, ui t){ //询问l到r区间内的集合是否都能异或出x if(l <= tree[k].l && r >= tree[k].r){ L_B temp = tree[k].node; return Insert(temp, t); //能异或出返回true } int mid = (tree[k].l + tree[k].r) >> 1; return (l <= mid? query(2*k, l, r, t): true) && (r > mid? query(2*k+1, l, r, t): true); //返回mid的左右部分是否都能异或出x } int main(){ scanf("%d%d", &n, &m); build(1, 1, n); while(m--){ int l, r; ui x; scanf("%d%d%u", &l, &r, &x); if(x == 0 || query(1, l, r, x)) printf("YES\n"); //特判x=0一定能异或出(空集异或出0) else printf("NO\n"); } return 0; }偷来的代码
后记:
- 线性基的交集还没有解决
标签:xor,int,tree,多校,mid,牛客,异或,ui,-- From: https://www.cnblogs.com/Lamboofhome/p/17330716.html