传送门
题意：给你一个数组，有两种操作，一种区间xor一个值，一个是查询区间xor的结果的种类数
对于一个给定的区间，我们可以通过求解线性基的方式求出结果的种类数，而现在只不过将其放在线段树上维护区间线性基。
#include <bits/stdc++.h> using namespace std; struct L_B { long long d[31]; void init() { memset(d, 0, sizeof(d)); } bool insert(long long val) { for (int i = 30; i >= 0; i--) if (val & (1 << i)) { if (!d[i]) { d[i] = val; break; } val ^= d[i]; } return val > 0; } int cnt() { int res = 0; for (int i = 30; i >= 0; --i) { if (d[i])res++; } return 1 << res; } }; struct node { L_B lb; int lazy, w; int l, r; } t[200004 * 4]; node merge(const node n1, const node n2) { //线性基合并 node ret = n1; for (int i = 30; i >= 0; i--) { if (n1.lb.d[i])ret.lb.insert(n1.lb.d[i]); if (n2.lb.d[i])ret.lb.insert(n2.lb.d[i]); } ret.lb.insert(n1.w ^ n2.w); ret.w = n2.w; return ret; } int a[200004]; void pu(int rt) {// 线段树更新 int l = t[rt].l; int r = t[rt].r; int lazy = t[rt].lazy; t[rt] = merge(t[rt << 1], t[rt << 1 | 1]); t[rt].l = l, t[rt].r = r, t[rt].lazy = lazy; } void build(int rt, int l, int r) { t[rt].l = l, t[rt].r = r, t[rt].lazy = 0; t[rt].lb.init(); if (l == r) { t[rt].w = a[l]; } else { int mid = (l + r) >> 1; build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r); pu(rt); } } void pushdown(int rt) { if (t[rt].lazy == 0)return; t[rt << 1].lazy ^= t[rt].lazy; t[rt << 1 | 1].lazy ^= t[rt].lazy; t[rt << 1].w ^= t[rt].lazy; t[rt << 1 | 1].w ^= t[rt].lazy; t[rt].lazy = 0; } void update(int rt, int l, int r, int xo) { // 区间更新 if (t[rt].l >= l && t[rt].r <= r) { t[rt].lazy ^= xo; t[rt].w ^= xo; } else { pushdown(rt); int mid = (t[rt].l + t[rt].r) >> 1; if (l <= mid)update(rt << 1, l, r, xo); if (r > mid)update(rt << 1 | 1, l, r, xo); pu(rt); } } void query(int rt, int l, int r, node &ans) { if (t[rt].l >= l && t[rt].r <= r) { ans = merge(ans, t[rt]); } else { pushdown(rt); int mid = (t[rt].l + t[rt].r) >> 1; if (l <= mid) { query(rt << 1, l, r, ans); } if (r > mid) { query(rt << 1 | 1, l, r, ans); } } } int main() { int n, q; cin >> n >> q; for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } build(1, 1, n); while (q--) { int op, l, r, k; scanf("%d", &op); if (op == 1) { scanf("%d%d%d", &l, &r, &k); update(1, l, r, k); } else { scanf("%d%d", &l, &r); node ans; ans.lb.init(); ans.w = 0; query(1, l, r, ans); printf("%d\n", ans.lb.cnt()); } } }原作者
