xor

思路

題目是要求$[l,r]$的所有集合是否都可以得到$x$，那么顯然我們可以對這$[l,r]$個線性基求交，然后再特判能否$x$能否插入，如果能插入，顯然輸出$NO$，否則就輸出$YES$，所以問題轉換成了如何求這$[l,r]$個集合的線性基交了。

有個最簡單的方法就是用線段樹來維護了，然后暴力的得到$[l,r]$中的$log(n)$個線性基交，然后再判斷是否有集合是無法構成$x$的即可。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h>#define mp make_pair #define pb push_back #define endl '\n' #define mid (l + r >> 1) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define ls rt << 1 #define rs rt << 1 | 1using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }// typedef unsigned int ui;const int N = 5e4 + 10;struct LinearBasis {ll base[35];void init() {memset(base, 0, sizeof base);}ll & operator [] (int pos) {return base[pos];}bool insert(ll x) {for(int i = 31; i >= 0; i--) {if(x >> i & 1) {if(!base[i]) {base[i] = x;return true;}x ^= base[i];}}return false;}bool judge(ll x) {for(int i = 31; i >= 0; i--) {if(x >> i & 1) {if(!base[i]) {return true;}x ^= base[i];}}return false;}LinearBasis inter (const LinearBasis & t) {LinearBasis ans, c = t, d = t;ans.init();for(int i = 0; i < 32; i++) {if(!base[i]) continue;int p = i;ll x = base[i], temp = 0;for(int j = p; j >= 0; j--) {if(x >> j & 1) {if(c[j]) {x ^= c[j]; temp ^= d[j];}else {p = j; break;}}}if(!x) {ans[i] = temp;}else {c[p] = x; d[p] = temp;}}return ans;} }tree[N << 2];void push_up(int rt) {tree[rt] = tree[ls].inter(tree[rs]); }void build(int rt, int l, int r) {if(l == r) {int n = read();for(int i = 1; i <= n; i++) {ll x = read();tree[rt].insert(x);}return ;}build(lson);build(rson);push_up(rt); }int flag;void query(int rt, int l, int r, int L, int R, ll x) {if(l >= L && r <= R) {if(tree[rt].judge(x)) flag = 0;return ;}if(L <= mid) query(lson, L, R, x);if(R > mid) query(rson, L, R, x); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int n = read(), m = read();build(1, 1, n);for(int i = 1; i <= m; i++) {int l = read(), r = read(); ll x = read(); flag = 1;query(1, 1, n, l, r, x);puts(flag ? "YES" : "NO");}return 0; }

總結

以上是生活随笔為你收集整理的2019牛客多校第四场 B xor (线性基求交)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。