Untitled

unknown
c_cpp
a month ago
4.4 kB
3
Indexable
Never
```#include <bits/stdc++.h>

using namespace std;

#define ll long long

void FIO() {
#ifndef ONLINE_JUDGE
freopen("../in.txt", "r", stdin);
freopen("../out.txt", "w", stdout);
#endif
}

const int MAX_BIT = 20;

struct basis {
vector<int> b;
int n;

void insert(int x) {
for (int i: b) {
x = min(x, i ^ x);
}
if (x) {
++n;
b.push_back(x);
for (int i = n - 1; i > 0; --i) {
if (b[i] > b[i - 1]) {
swap(b[i], b[i - 1]);
}
}
}
}

void join(const basis &other) {
if (n == MAX_BIT) return;
for (int i: other.b) {
insert(i);
}
}

int get_mx() {
int res = 0;
// sorted in decreasing order
for (int i: b) {
res = max(res, res ^ i);
}
return res;
}

basis() : n(0) {}
};

basis merge(const basis &a, const basis &b) {
basis res = a;
res.join(b);
return res;
}

struct item {
int x;
basis b;

void insert(int y) {
b.insert(y);
}

void clear() {
b = basis();
}

item() : x(-1) {}
};

struct segTree {
vector<item> tree;
int size;

void init(int n) {
size = 1;
while (size < n) size *= 2;
tree.assign(2 * size, item());
}

void propagate(int x, int lx, int rx) {
if (tree[x].x == -1) return;
if (rx - lx != 1) {
tree[2 * x + 1].x &= tree[x].x;
tree[2 * x + 2].x &= tree[x].x;
}

basis b = tree[x].b;
tree[x].clear();
for (int i: b.b) {
tree[x].insert(i & tree[x].x);
}
tree[x].x = -1;
}

void build(vector<int> &a, int x, int lx, int rx) {
if (rx - lx == 1) {
if (lx < a.size()) {
tree[x].insert(a[lx]);
}
return;
}
int m = (lx + rx) / 2;
build(a, 2 * x + 1, lx, m);
build(a, 2 * x + 2, m, rx);
tree[x].b = merge(tree[2 * x + 1].b, tree[2 * x + 2].b);
}

void build(vector<int> &a) {
init(a.size());
build(a, 0, 0, size);
}

void update(int l, int r, int v, int x, int lx, int rx) {
propagate(x, lx, rx);
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r) {
tree[x].x = v;
propagate(x, lx, rx);
return;
}

int m = (lx + rx) / 2;
update(l, r, v, 2 * x + 1, lx, m);
update(l, r, v, 2 * x + 2, m, rx);
tree[x].b = merge(tree[2 * x + 1].b, tree[2 * x + 2].b);
}

void update(int l, int r, int v) {
update(l, r, v, 0, 0, size);
}

void set(int i, int v, int x, int lx, int rx) {
propagate(x, lx, rx);
if (lx > i || rx <= i) return;
if (rx - lx == 1) {
tree[x].clear();
tree[x].insert(v);
return;
}
int m = (lx + rx) / 2;
set(i, v, 2 * x + 1, lx, m);
set(i, v, 2 * x + 2, m, rx);
tree[x].b = merge(tree[2 * x + 1].b, tree[2 * x + 2].b);
}

void set(int i, int v) {
set(i, v, 0, 0, size);
}

basis query(int l, int r, int x, int lx, int rx) {
propagate(x, lx, rx);
if (lx >= r || rx <= l) return basis();
if (lx >= l && rx <= r) return tree[x].b;
int m = (lx + rx) / 2;
basis s1 = query(l, r, 2 * x + 1, lx, m);
basis s2 = query(l, r, 2 * x + 2, m, rx);
return merge(s1, s2);
}

basis query(int l, int r) {
return query(l, r, 0, 0, size);
}
};

void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
segTree st;
st.build(a);
while (q--) {
int t;
cin >> t;
if (t == 1) {
int l, r, v;
cin >> l >> r >> v;
st.update(l - 1, r, v);
} else if (t == 2) {
int i, v;
cin >> i >> v;
st.set(i - 1, v);
} else {
int l, r;
cin >> l >> r;
cout << st.query(l - 1, r).get_mx() << '\n';
}
}
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
FIO();

int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}```