static_range_xor_basis.hpp¶
为静态数组区间建立线性基，回答子集异或最大值、可达性或秩等查询。
Complexity: Time: O(nB) build and O(B) query for B-bit values. Space: O(nB).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(nB) build and O(B) query for B-bit values.
/// Space: O(nB).
#include "noya/xor_basis.hpp"
#include <array>
#include <cassert>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Prefix-persistent linear bases for maximum xor and membership in a
/// static subarray, with O(B) queries and O(nB) preprocessing.
template <class UInt, int B = std::numeric_limits<UInt>::digits>
struct static_range_xor_basis {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < B && B <= std::numeric_limits<UInt>::digits);
struct entry {
UInt val = 0;
int pos = -1;
};
int n = 0;
std::vector<std::array<entry, B>> pre;
static_range_xor_basis() = default;
explicit static_range_xor_basis(const std::vector<UInt> &a) { build(a); }
void build(const std::vector<UInt> &a) {
n = int(a.size());
pre.assign(n + 1, {});
for (int pos = 0; pos < n; pos++) {
pre[pos + 1] = pre[pos];
insert(pre[pos + 1], a[pos], pos);
}
}
/// @brief Maximize seed xor x over subset x of values[l, r).
UInt max_xor(int l, int r, UInt rng = 0) const {
check_range(l, r);
const auto &bs = pre[r];
for (int bit = B - 1; bit >= 0; bit--) {
if (bs[bit].pos >= l && (rng ^ bs[bit].val) > rng) {
rng ^= bs[bit].val;
}
}
return rng;
}
/// @brief Minimize seed xor x over subset x of values[l, r).
UInt min_xor(int l, int r, UInt rng) const {
check_range(l, r);
const auto &bs = pre[r];
for (int bit = B - 1; bit >= 0; bit--) {
if (bs[bit].pos >= l && (rng ^ bs[bit].val) < rng) {
rng ^= bs[bit].val;
}
}
return rng;
}
/// @brief Return whether value is an xor of a subset of values[l,r).
bool contains(int l, int r, UInt val) const {
check_range(l, r);
const auto &bs = pre[r];
for (int bit = B - 1; bit >= 0; bit--) {
if ((val >> bit) & UInt(1)) {
if (bs[bit].pos < l) {
return false;
}
val ^= bs[bit].val;
}
}
return true;
}
int dimension(int l, int r) const {
check_range(l, r);
int res = 0;
for (const entry &x : pre[r]) {
res += x.pos >= l;
}
return res;
}
/// @brief Materialize an ordinary xor basis of a subarray.
xor_basis<UInt, B> range_basis(int l, int r) const {
check_range(l, r);
xor_basis<UInt, B> res;
for (const entry &x : pre[r]) {
if (x.pos >= l) {
res.insert(x.val);
}
}
return res;
}
private:
static void insert(std::array<entry, B> &bs, UInt val, int pos) {
for (int bit = B - 1; bit >= 0 && val != 0; bit--) {
if (((val >> bit) & UInt(1)) == 0) {
continue;
}
if (bs[bit].val == 0) {
bs[bit] = {val, pos};
return;
}
if (pos > bs[bit].pos) {
std::swap(val, bs[bit].val);
std::swap(pos, bs[bit].pos);
}
val ^= bs[bit].val;
}
}
void check_range(int l, int r) const { assert(0 <= l && l <= r && r <= n); }
};
} // namespace noya
#ifndef NOYA_STATIC_RANGE_XOR_BASIS_HPP
#define NOYA_STATIC_RANGE_XOR_BASIS_HPP 1
/// @complexity Time: O(nB) build and O(B) query for B-bit values.
/// Space: O(nB).
#include "noya/xor_basis.hpp"
#include <array>
#include <cassert>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Prefix-persistent linear bases for maximum xor and membership in a
/// static subarray, with O(B) queries and O(nB) preprocessing.
template <class UInt, int B = std::numeric_limits<UInt>::digits>
struct static_range_xor_basis {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < B && B <= std::numeric_limits<UInt>::digits);
struct entry {
UInt val = 0;
int pos = -1;
};
int n = 0;
std::vector<std::array<entry, B>> pre;
static_range_xor_basis() = default;
explicit static_range_xor_basis(const std::vector<UInt> &a) { build(a); }
void build(const std::vector<UInt> &a) {
n = int(a.size());
pre.assign(n + 1, {});
for (int pos = 0; pos < n; pos++) {
pre[pos + 1] = pre[pos];
insert(pre[pos + 1], a[pos], pos);
}
}
/// @brief Maximize seed xor x over subset x of values[l, r).
UInt max_xor(int l, int r, UInt rng = 0) const {
check_range(l, r);
const auto &bs = pre[r];
for (int bit = B - 1; bit >= 0; bit--) {
if (bs[bit].pos >= l && (rng ^ bs[bit].val) > rng) {
rng ^= bs[bit].val;
}
}
return rng;
}
/// @brief Minimize seed xor x over subset x of values[l, r).
UInt min_xor(int l, int r, UInt rng) const {
check_range(l, r);
const auto &bs = pre[r];
for (int bit = B - 1; bit >= 0; bit--) {
if (bs[bit].pos >= l && (rng ^ bs[bit].val) < rng) {
rng ^= bs[bit].val;
}
}
return rng;
}
/// @brief Return whether value is an xor of a subset of values[l,r).
bool contains(int l, int r, UInt val) const {
check_range(l, r);
const auto &bs = pre[r];
for (int bit = B - 1; bit >= 0; bit--) {
if ((val >> bit) & UInt(1)) {
if (bs[bit].pos < l) {
return false;
}
val ^= bs[bit].val;
}
}
return true;
}
int dimension(int l, int r) const {
check_range(l, r);
int res = 0;
for (const entry &x : pre[r]) {
res += x.pos >= l;
}
return res;
}
/// @brief Materialize an ordinary xor basis of a subarray.
xor_basis<UInt, B> range_basis(int l, int r) const {
check_range(l, r);
xor_basis<UInt, B> res;
for (const entry &x : pre[r]) {
if (x.pos >= l) {
res.insert(x.val);
}
}
return res;
}
private:
static void insert(std::array<entry, B> &bs, UInt val, int pos) {
for (int bit = B - 1; bit >= 0 && val != 0; bit--) {
if (((val >> bit) & UInt(1)) == 0) {
continue;
}
if (bs[bit].val == 0) {
bs[bit] = {val, pos};
return;
}
if (pos > bs[bit].pos) {
std::swap(val, bs[bit].val);
std::swap(pos, bs[bit].pos);
}
val ^= bs[bit].val;
}
}
void check_range(int l, int r) const { assert(0 <= l && l <= r && r <= n); }
};
} // namespace noya
#endif // NOYA_STATIC_RANGE_XOR_BASIS_HPP
#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>
/// @complexity Time: O(nB) build and O(B) query for B-bit values.
/// Space: O(nB).
/// @complexity Time: O(B^2) reduced insertion and O(B) membership/min/max query.
/// Space: O(B).
namespace noya {
/// @brief Reduced linear basis over GF(2) for an unsigned integer type.
template <class UInt, int bts = std::numeric_limits<UInt>::digits>
struct xor_basis {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < bts && bts <= std::numeric_limits<UInt>::digits);
std::array<UInt, bts> bas{};
int dim = 0;
/// @brief Insert a value; return false if it is already in the span.
bool insert(UInt val) {
for (int bit = bts - 1; bit >= 0; bit--) {
if (((val >> bit) & UInt(1)) == 0) {
continue;
}
if (bas[bit] != 0) {
val ^= bas[bit];
continue;
}
bas[bit] = val;
for (int lo = 0; lo < bit; lo++) {
if ((bas[bit] >> lo) & UInt(1)) {
bas[bit] ^= bas[lo];
}
}
for (int hig = bit + 1; hig < bts; hig++) {
if ((bas[hig] >> bit) & UInt(1)) {
bas[hig] ^= bas[bit];
}
}
dim++;
return true;
}
return false;
}
/// @brief Return whether value belongs to the represented xor span.
bool contains(UInt val) const {
for (int bit = bts - 1; bit >= 0; bit--) {
if ((val >> bit) & UInt(1)) {
val ^= bas[bit];
}
}
return val == 0;
}
/// @brief Maximize seed xor x over all represented values x.
UInt max_xor(UInt see = 0) const {
for (int bit = bts - 1; bit >= 0; bit--) {
if ((see ^ bas[bit]) > see) {
see ^= bas[bit];
}
}
return see;
}
/// @brief Minimize seed xor x over all represented values x.
UInt min_xor(UInt see) const {
for (int bit = bts - 1; bit >= 0; bit--) {
if ((see ^ bas[bit]) < see) {
see ^= bas[bit];
}
}
return see;
}
/// @brief Return the k-th smallest distinct value in the span, including
/// zero.
UInt kth_smallest(std::uint64_t k) const {
if (dim < 64) {
assert(k < (std::uint64_t(1) << dim));
}
UInt res = 0;
int idx = 0;
for (int bit = 0; bit < bts; bit++) {
if (bas[bit] != 0) {
if ((k >> idx) & 1) {
res ^= bas[bit];
}
idx++;
}
}
return res;
}
/// @brief Insert every basis vector from another span.
void merge(const xor_basis &oth) {
for (UInt val : oth.bas) {
if (val != 0) {
insert(val);
}
}
}
};
/// @brief Return a basis of the intersection of two xor spans. A homogeneous
/// system is built for U*a = V*b, with one equation per value bit. Gaussian
/// elimination produces a nullspace basis; projecting its U-coordinates gives
/// an independent basis of the intersection because both input lists are
/// required to be independent.
template <class UInt, int bts = std::numeric_limits<UInt>::digits>
std::vector<UInt> xor_space_intersection(const std::vector<UInt> &a,
const std::vector<UInt> &b) {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < bts && bts <= std::numeric_limits<UInt>::digits);
const int ls = int(a.size());
const int vc = ls + int(b.size());
assert(vc <= 64);
xor_basis<UInt, bts> lc;
xor_basis<UInt, bts> rc;
for (UInt val : a) {
assert(lc.insert(val));
}
for (UInt val : b) {
assert(rc.insert(val));
}
std::array<std::uint64_t, bts> equ{};
for (int var = 0; var < vc; var++) {
UInt val = var < ls ? a[var] : b[var - ls];
for (int bit = 0; bit < bts; bit++) {
if ((val >> bit) & UInt(1)) {
equ[bit] |= std::uint64_t(1) << var;
}
}
}
std::array<int, 64> pr{};
pr.fill(-1);
int ran = 0;
for (int col = 0; col < vc; col++) {
int piv = ran;
while (piv < bts && ((equ[piv] >> col) & 1) == 0) {
piv++;
}
if (piv == bts) {
continue;
}
std::swap(equ[ran], equ[piv]);
pr[col] = ran;
for (int row = 0; row < bts; row++) {
if (row != ran && ((equ[row] >> col) & 1)) {
equ[row] ^= equ[ran];
}
}
ran++;
}
std::vector<UInt> res;
for (int fc = 0; fc < vc; fc++) {
if (pr[fc] != -1) {
continue;
}
std::uint64_t cf = std::uint64_t(1) << fc;
for (int col = 0; col < vc; col++) {
int row = pr[col];
if (row != -1 && ((equ[row] >> fc) & 1)) {
cf |= std::uint64_t(1) << col;
}
}
UInt val = 0;
for (int idx = 0; idx < ls; idx++) {
if ((cf >> idx) & 1) {
val ^= a[idx];
}
}
res.push_back(val);
}
return res;
}
} // namespace noya
namespace noya {
/// @brief Prefix-persistent linear bases for maximum xor and membership in a
/// static subarray, with O(B) queries and O(nB) preprocessing.
template <class UInt, int B = std::numeric_limits<UInt>::digits>
struct static_range_xor_basis {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < B && B <= std::numeric_limits<UInt>::digits);
struct entry {
UInt val = 0;
int pos = -1;
};
int n = 0;
std::vector<std::array<entry, B>> pre;
static_range_xor_basis() = default;
explicit static_range_xor_basis(const std::vector<UInt> &a) { build(a); }
void build(const std::vector<UInt> &a) {
n = int(a.size());
pre.assign(n + 1, {});
for (int pos = 0; pos < n; pos++) {
pre[pos + 1] = pre[pos];
insert(pre[pos + 1], a[pos], pos);
}
}
/// @brief Maximize seed xor x over subset x of values[l, r).
UInt max_xor(int l, int r, UInt rng = 0) const {
check_range(l, r);
const auto &bs = pre[r];
for (int bit = B - 1; bit >= 0; bit--) {
if (bs[bit].pos >= l && (rng ^ bs[bit].val) > rng) {
rng ^= bs[bit].val;
}
}
return rng;
}
/// @brief Minimize seed xor x over subset x of values[l, r).
UInt min_xor(int l, int r, UInt rng) const {
check_range(l, r);
const auto &bs = pre[r];
for (int bit = B - 1; bit >= 0; bit--) {
if (bs[bit].pos >= l && (rng ^ bs[bit].val) < rng) {
rng ^= bs[bit].val;
}
}
return rng;
}
/// @brief Return whether value is an xor of a subset of values[l,r).
bool contains(int l, int r, UInt val) const {
check_range(l, r);
const auto &bs = pre[r];
for (int bit = B - 1; bit >= 0; bit--) {
if ((val >> bit) & UInt(1)) {
if (bs[bit].pos < l) {
return false;
}
val ^= bs[bit].val;
}
}
return true;
}
int dimension(int l, int r) const {
check_range(l, r);
int res = 0;
for (const entry &x : pre[r]) {
res += x.pos >= l;
}
return res;
}
/// @brief Materialize an ordinary xor basis of a subarray.
xor_basis<UInt, B> range_basis(int l, int r) const {
check_range(l, r);
xor_basis<UInt, B> res;
for (const entry &x : pre[r]) {
if (x.pos >= l) {
res.insert(x.val);
}
}
return res;
}
private:
static void insert(std::array<entry, B> &bs, UInt val, int pos) {
for (int bit = B - 1; bit >= 0 && val != 0; bit--) {
if (((val >> bit) & UInt(1)) == 0) {
continue;
}
if (bs[bit].val == 0) {
bs[bit] = {val, pos};
return;
}
if (pos > bs[bit].pos) {
std::swap(val, bs[bit].val);
std::swap(pos, bs[bit].pos);
}
val ^= bs[bit].val;
}
}
void check_range(int l, int r) const { assert(0 <= l && l <= r && r <= n); }
};
} // namespace noya