static_range_xor_basis.hpp¶
静态半开区间线性基：O(NB) 构建，O(B) 查询子集异或最值、可达性和秩，O(B²) 导出约化基；输入须在 B 位内。
Complexity: Time: \(O(nB)\) build, \(O(B)\) queries, \(O(B^{2})\) range_basis. Space: \(O((n + 1) B)\). Values fit in \(B\) bits; \(n\) fits int.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(nB) build, O(B) queries, O(B^2) range_basis.
/// Space: O((n+1)B). Values fit in B bits; n fits int.
#include "noya/math/xor_basis.hpp"
#include <array>
#include <bit>
#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) {
assert(a.size() <= std::size_t(std::numeric_limits<int>::max()));
n = int(a.size());
pre.clear();
pre.reserve(a.size() + 1);
pre.emplace_back();
for (int pos = 0; pos < n; pos++) {
if constexpr (B < std::numeric_limits<UInt>::digits)
assert((a[pos] >> B) == 0);
// Initialize each row only once, from the preceding prefix.
pre.push_back(pre.back());
insert(pre.back(), 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);
if (l == r)
return rng;
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);
if (l == r)
return rng;
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);
if (l == r)
return val == 0;
const auto &bs = pre[r];
while (val != 0) {
int bit = highest_bit(val);
if (bit >= B || bs[bit].pos < l)
return false;
val ^= bs[bit].val;
}
return true;
}
int dimension(int l, int r) const {
check_range(l, r);
if (l == r)
return 0;
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;
if (l == r)
return res;
// Pivots are already distinct. Reduce only against earlier, lower rows.
for (int bit = 0; bit < B; ++bit) {
if (pre[r][bit].pos < l)
continue;
UInt val = pre[r][bit].val;
for (int lo = 0; lo < bit; ++lo)
if ((val >> lo) & UInt(1))
val ^= res.bas[lo];
res.bas[bit] = val;
++res.dim;
}
return res;
}
private:
// The cast also supports bool and narrow unsigned integral types.
static int highest_bit(UInt val) {
if constexpr (std::numeric_limits<UInt>::digits <=
std::numeric_limits<unsigned long long>::digits)
return std::bit_width(static_cast<unsigned long long>(val)) - 1;
else
return std::bit_width(val) - 1;
}
static void insert(std::array<entry, B> &bs, UInt val, int pos) {
while (val != 0) {
int bit = highest_bit(val);
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
// NOYA_STATIC_RANGE_XOR_BASIS_HPP
#ifndef NOYA_STATIC_RANGE_XOR_BASIS_HPP
#define NOYA_STATIC_RANGE_XOR_BASIS_HPP 1
/// @complexity Time: O(nB) build, O(B) queries, O(B^2) range_basis.
/// Space: O((n+1)B). Values fit in B bits; n fits int.
#include "noya/math/xor_basis.hpp"
#include <array>
#include <bit>
#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) {
assert(a.size() <= std::size_t(std::numeric_limits<int>::max()));
n = int(a.size());
pre.clear();
pre.reserve(a.size() + 1);
pre.emplace_back();
for (int pos = 0; pos < n; pos++) {
if constexpr (B < std::numeric_limits<UInt>::digits)
assert((a[pos] >> B) == 0);
// Initialize each row only once, from the preceding prefix.
pre.push_back(pre.back());
insert(pre.back(), 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);
if (l == r)
return rng;
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);
if (l == r)
return rng;
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);
if (l == r)
return val == 0;
const auto &bs = pre[r];
while (val != 0) {
int bit = highest_bit(val);
if (bit >= B || bs[bit].pos < l)
return false;
val ^= bs[bit].val;
}
return true;
}
int dimension(int l, int r) const {
check_range(l, r);
if (l == r)
return 0;
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;
if (l == r)
return res;
// Pivots are already distinct. Reduce only against earlier, lower rows.
for (int bit = 0; bit < B; ++bit) {
if (pre[r][bit].pos < l)
continue;
UInt val = pre[r][bit].val;
for (int lo = 0; lo < bit; ++lo)
if ((val >> lo) & UInt(1))
val ^= res.bas[lo];
res.bas[bit] = val;
++res.dim;
}
return res;
}
private:
// The cast also supports bool and narrow unsigned integral types.
static int highest_bit(UInt val) {
if constexpr (std::numeric_limits<UInt>::digits <=
std::numeric_limits<unsigned long long>::digits)
return std::bit_width(static_cast<unsigned long long>(val)) - 1;
else
return std::bit_width(val) - 1;
}
static void insert(std::array<entry, B> &bs, UInt val, int pos) {
while (val != 0) {
int bit = highest_bit(val);
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
/// @complexity Time: O(nB) build, O(B) queries, O(B^2) range_basis.
/// Space: O((n+1)B). Values fit in B bits; n fits int.
/// @complexity Time: O(B) insertion/query and O(B^2) merge/intersection.
/// Space: O(B).
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <vector>
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 fitting bts bits; return false if already in the span.
bool insert(UInt val) {
if constexpr (bts < std::numeric_limits<UInt>::digits)
assert((val >> bts) == 0);
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 (idx < 64 && ((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. Both input
/// lists must be independent, with values fitting bts bits. Eliminate the
/// first space, then the second, carrying each vector's contribution from the
/// first space. A vector reduced to zero yields a vector in both spaces.
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);
xor_basis<UInt, bts> lc, rc;
for (UInt val : a) assert(lc.insert(val));
for (UInt val : b) assert(rc.insert(val));
std::array<UInt, bts> bas{}, src{};
auto ins = [&](UInt x, UInt y) {
for (int i = bts - 1; i >= 0; --i) {
if (((x >> i) & UInt(1)) == 0) continue;
if (bas[i]) {
x ^= bas[i];
y ^= src[i];
} else {
bas[i] = x;
src[i] = y;
return UInt(0);
}
}
return y;
};
for (UInt x : a) ins(x, x);
std::vector<UInt> res;
res.reserve(std::min(a.size(), b.size()));
for (UInt x : b) {
UInt y = ins(x, UInt(0));
if (y) res.push_back(y);
}
return res;
}
} // namespace noya
#include <array>
#include <bit>
#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) {
assert(a.size() <= std::size_t(std::numeric_limits<int>::max()));
n = int(a.size());
pre.clear();
pre.reserve(a.size() + 1);
pre.emplace_back();
for (int pos = 0; pos < n; pos++) {
if constexpr (B < std::numeric_limits<UInt>::digits)
assert((a[pos] >> B) == 0);
// Initialize each row only once, from the preceding prefix.
pre.push_back(pre.back());
insert(pre.back(), 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);
if (l == r)
return rng;
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);
if (l == r)
return rng;
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);
if (l == r)
return val == 0;
const auto &bs = pre[r];
while (val != 0) {
int bit = highest_bit(val);
if (bit >= B || bs[bit].pos < l)
return false;
val ^= bs[bit].val;
}
return true;
}
int dimension(int l, int r) const {
check_range(l, r);
if (l == r)
return 0;
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;
if (l == r)
return res;
// Pivots are already distinct. Reduce only against earlier, lower rows.
for (int bit = 0; bit < B; ++bit) {
if (pre[r][bit].pos < l)
continue;
UInt val = pre[r][bit].val;
for (int lo = 0; lo < bit; ++lo)
if ((val >> lo) & UInt(1))
val ^= res.bas[lo];
res.bas[bit] = val;
++res.dim;
}
return res;
}
private:
// The cast also supports bool and narrow unsigned integral types.
static int highest_bit(UInt val) {
if constexpr (std::numeric_limits<UInt>::digits <=
std::numeric_limits<unsigned long long>::digits)
return std::bit_width(static_cast<unsigned long long>(val)) - 1;
else
return std::bit_width(val) - 1;
}
static void insert(std::array<entry, B> &bs, UInt val, int pos) {
while (val != 0) {
int bit = highest_bit(val);
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
// NOYA_STATIC_RANGE_XOR_BASIS_HPP