[UOJ91]最大异或和
可删除线性基。
有一个数列 \(a_1,a_2,\dots,a_n\)，每个 \(a_i\) 都是小于 \(2^m\) 的非负整数。
现在需要实现三种操作，格式说明如下：
- 1 x y w：对于所有 \(x≤i≤y\)，将 \(a_i\) 修改为 \(a_i\oplus w\)。其中 \(w\) 是一个小于 \(2^m\) 的非负整数。
- 2 x y w：对于所有 \(x≤i≤y\)，将 \(a_i\) 修改为 \(w\)。其中 \(w\) 是一个小于 \(2^m\) 的非负整数。
- 3：从 \(a_1,a_2,⋯,a_n\) 中选出若干个数，使得选出的数异或和最大。请输出这个最大值。
这里 \(\oplus\) 表示按位异或运算，\(x_1,x_2,⋯,x_l\) 的异或和是指 \(x_1\oplus x_2\oplus \cdots\oplus x_l\)。
\(n,m,q≤2000\)。
将原序列差分，线性基不变。
然后每次操作就是单点插入和删除，下面给出两种可删除线性基的写法。
离线
记录存活时间，贪心。
using BS = std::bitset<2000>;
using PBI = std::pair<BS, int>;
PBI base[2000];
void ins(PBI x) {
for (int i = 1999; i >= 0; i--) {
if (!x.first[i]) continue;
if (x.second > base[i].second) {
std::swap(x, base[i]);
if (!x.second) break;
}
x.first ^= base[i].first;
}
}在线
\[ PV=B \]
\[ \det(P)\neq 0, V = \begin{pmatrix} v_1\\ v_2\\ \vdots\\ v_n \end{pmatrix}, B= \begin{pmatrix} base_1\\ \vdots\\ 0\\ \vdots\\ base_m\\ \vdots\\ 0\\ \vdots \end{pmatrix} \]
记录可逆矩阵 \(P\)，修改 \(v_i\) 时，要将 \(P\) 的第 \(i\) 列全部变成0。
为了尽量在不影响 \(B\) 的情况下消元，首先找 \(j\) 满足 \(P_{i,j}=1,i\neq j, base_j=0\)。
如果找到这样的 \(j\) 那么直接消元，\(B\) 不会有任何变化。
如果没有找到，那么需要找最小的 \(base_k\) 使得 \(base_k\) 包含 \(v_i\)，然后用 \(base_k\) 消去其他包含 \(v_i\) 的 \(base\)。
Code
离线
// Author: HolyK
// Created: Mon Jul 5 14:24:21 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
using BS = std::bitset<2000>;
using PBI = std::pair<BS, int>;
int n, m, q;
PBI base[2000];
void ins(PBI x) {
for (int i = m - 1; i >= 0; i--) {
if (!x.first[i]) continue;
if (x.second > base[i].second) {
std::swap(x, base[i]);
if (!x.second) break;
}
x.first ^= base[i].first;
}
}
BS a[2005];
std::vector<PBI> g[2005];
int t[2005];
bool ask[2005];
char tmp[2005];
int main() {
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++) {
scanf("%s", tmp);
for (int j = 0; j < m; j++) a[i][j] = tmp[m - 1- j] ^ '0';
}
for (int i = 1; i <= q; i++) {
int opt;
scanf("%d", &opt);
if (opt == 3) {
ask[i] = true;
} else {
int x, y;
BS z;
scanf("%d%d", &x, &y);
scanf("%s", tmp);
for (int j = 0; j < m; j++) z[j] = tmp[m - 1- j] ^ '0';
y++;
if (opt == 1) {
if (t[x] != -1) g[t[x]].emplace_back(a[x] ^ a[x - 1], i - 1);
if (t[y] != -1) g[t[y]].emplace_back(a[y] ^ a[y - 1], i - 1);
for (int j = x; j < y; j++) a[j] ^= z;
t[x] = t[y] = i;
} else {
for (int j = x; j <= y && j <= n; j++) {
if (t[j] != -1) g[t[j]].emplace_back(a[j] ^ a[j - 1], i - 1);
t[j] = -1;
}
for (int j = x; j < y; j++) a[j] = z;
t[x] = t[y] = i;
}
}
}
for (int i = 1; i <= n; i++) if (t[i] != -1) g[t[i]].emplace_back(a[i] ^ a[i - 1], q);
for (int i = 0; i <= q; i++) {
for (auto &v : g[i]) ins(v);
if (!ask[i]) continue;
BS ans;
for (int j = m - 1; j >= 0; j--) {
if (base[j].second >= i && !ans[j]) ans ^= base[j].first;
}
for (int j = m - 1; j >= 0; j--) putchar("01"[ans[j]]);
puts("");
}
return 0;
}在线
// Author: HolyK
// Created: Mon Jul 5 15:29:33 2021
#include <bits/stdc++.h>
#define dbg(a...) fprintf(stderr, a)
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(2005);
using BS = std::bitset<N>;
int n, m, q;
int base[N];
BS a[N], v[N], p[N];
void ins(int id) {
for (int i = m - 1; i >= 0; i--) {
if (!v[id][i]) continue;
if (!base[i]) {
base[i] = id;
return;
}
v[id] ^= v[base[i]];
p[id] ^= p[base[i]];
}
}
void update(int id, const BS &z) {
if (z.none()) return;
int j = 0;
for (int i = 1; i <= n; i++) {
if (v[i].any() || !p[i][id]) continue;
j = i;
break;
}
if (!j) {
for (int i = 0; i < m; i++) {
if (!base[i] || !p[base[i]][id]) continue;
j = base[i];
base[i] = 0;
break;
}
}
assert(j);
for (int i = 1; i <= n; i++) {
if (i == j || !p[i][id]) continue;
v[i] ^= v[j];
p[i] ^= p[j];
}
v[j] ^= z;
ins(j);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m >> q;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
v[i] = a[i] ^ a[i - 1];
p[i].set(i);
ins(i);
}
while (q--) {
int opt, x, y;
BS z;
std::cin >> opt;
if (opt == 1) {
std::cin >> x >> y >> z;
update(x, z);
if (y < n) update(y + 1, z);
for (int i = x; i <= y; i++) a[i] ^= z;
} else if (opt == 2) {
std::cin >> x >> y >> z;
update(x, a[x] ^ z);
if (y < n) update(y + 1, a[y] ^ z);
for (int i = x; i < y; i++) update(i + 1, a[i] ^ a[i + 1]);
for (int i = x; i <= y; i++) a[i] = z;
} else {
z.reset();
for (int i = m - 1; i >= 0; std::cout << z[i--]) {
if (base[i] && !z[i]) z ^= v[base[i]];
}
std::cout << "\n";
}
}
return 0;
}最后修改于 2021-08-13