static_range_inversions.hpp¶
按值扫描预处理块间逆序对，并压缩重复值；之后可在线回答任意半开区间的严格逆序对数量，空区间为零。
Complexity: Time: \(O(n \log n + n \sqrt{n})\) preprocessing with linear sort workspace, \(O(\sqrt{n})\) per query. Space: \(O(1 + n + d \sqrt{n})\), \(d\) distinct values.
Source: Library Checker
AC 记录：static_range_inversions_query。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(n log n + n sqrt(n)) preprocessing with linear sort
/// workspace, O(sqrt(n)) per query. Space: O(1+n+d sqrt(n)), d distinct values.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Static inversion counts for arbitrary online half-open queries.
/// Counts pairs i < j with a[j] < a[i]; equivalent values are not inversions.
/// Values need only strict weak ordering; bounds assume O(1) comparisons and
/// an int-sized array. The default-constructed object is empty. Rebuilding
/// may retain capacity from earlier builds beyond the stated fresh-build space.
template <class T> class static_range_inversions {
using count_type = std::uint64_t;
struct bucket {
std::vector<int> rk, ord, pf;
std::vector<count_type> pi, bi, pe;
};
int n_ = 0;
int bs_ = 1;
std::vector<bucket> bs;
public:
static_range_inversions() = default;
explicit static_range_inversions(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
n_ = int(a.size());
bs_ = int(std::sqrt(std::max(1, n_))) + 1;
std::vector<int> order(n_);
std::iota(order.begin(), order.end(), 0);
std::stable_sort(order.begin(), order.end(),
[&](int l, int r) { return a[l] < a[r]; });
std::vector<int> rk(n_);
int d = 0;
for (int i = 0; i < n_; ++i) {
if (i == 0 || a[order[i - 1]] < a[order[i]]) ++d;
rk[order[i]] = d - 1;
}
// The final bucket also represents r == n when n is a block multiple.
bs.assign(n_ / bs_ + 1, {});
for (int rb = 0; rb < int(bs.size()); ++rb) {
bucket &cur = bs[rb];
int arr = rb * bs_, len = std::min(bs_, n_ - arr);
cur.rk.assign(rk.begin() + arr, rk.begin() + arr + len);
cur.ord.reserve(len);
cur.pi.resize(len + 1);
cur.pe.resize(len + 1);
cur.bi.resize(rb);
}
// Stable global order also gives each block's sorted position order.
for (int pos : order) bs[pos / bs_].ord.push_back(pos % bs_);
std::vector<int> cnt(d), equal(d);
for (bucket &cur : bs) {
int len = int(cur.rk.size());
cur.pf.resize(std::size_t(d) + 1);
for (int v = 0; v < d; ++v) cur.pf[v + 1] = cur.pf[v] + cnt[v];
for (int v : cur.rk) ++cnt[v];
std::vector<int> local(len), bit(len + 1);
for (int i = 0; i < len; ++i) local[cur.ord[i]] = i;
for (int i = 0; i < len; ++i) {
int less = 0;
for (int p = local[i]; p; p -= p & -p) less += bit[p];
cur.pi[i + 1] = cur.pi[i] + i - less;
for (int p = local[i] + 1; p <= len; p += p & -p) ++bit[p];
cur.pe[i + 1] = cur.pe[i] + equal[cur.rk[i]]++;
}
for (int v : cur.rk) equal[v] = 0;
}
// A new smaller value makes inversions with greater values in left blocks.
// Reverse stable order processes equal values right-to-left, excluding them.
std::vector<int> seen(bs.size());
for (int i = n_; i-- > 0;) {
int rb = order[i] / bs_;
if (rb + 1 < int(bs.size())) {
auto &row = bs[rb + 1].bi;
for (int lb = 0; lb < rb; ++lb) row[lb] += seen[lb];
}
++seen[rb];
}
for (int rb = 0; rb + 1 < int(bs.size()); ++rb) {
auto &row = bs[rb + 1].bi;
count_type inv = bs[rb].pi.back();
row[rb] = inv;
for (int lb = rb; lb-- > 0;) {
inv += row[lb];
row[lb] = bs[rb].bi[lb] + inv;
}
}
}
int size() const { return n_; }
count_type inversions(int arr, int lst) const {
assert(0 <= arr && arr <= lst && lst <= n_);
if (arr == lst) return 0;
int bl = arr / bs_, pl = arr % bs_;
int br = lst / bs_, pr = lst % bs_;
const bucket &l = bs[bl];
const bucket &r = bs[br];
if (bl == br) {
count_type res = l.pi[pr] - l.pi[pl];
if (pl == 0) return res;
int num = 0;
for (int idx : l.ord) {
if (idx < pl) res -= num;
else if (idx < pr) ++num;
}
return res;
}
count_type res = r.bi[bl];
for (int i = 0; i < pl; ++i) res -= r.pf[l.rk[i]] - l.pf[l.rk[i]];
// Strict frequency subtraction also removes increasing pairs inside the
// left prefix. Add them back, excluding inversions and equal pairs.
res += count_type(pl) * (pl - 1) / 2 - l.pi[pl] - l.pe[pl];
res += r.pi[pr];
res += count_type(br - bl) * bs_ * pr;
// A right element forms inversions only with strictly greater left values.
for (int i = 0; i < pr; ++i)
res -= r.pf[r.rk[i] + 1] - l.pf[r.rk[i] + 1];
if (pl == 0 || pr == 0) return res;
int num = 0;
auto ri = r.ord.begin();
for (int idx : l.ord) {
while (ri != r.ord.end() && r.rk[*ri] < l.rk[idx]) {
if (*ri < pr) ++num;
++ri;
}
if (idx < pl) res -= num;
}
return res;
}
};
} // namespace noya
// NOYA_STATIC_RANGE_INVERSIONS_HPP
#ifndef NOYA_STATIC_RANGE_INVERSIONS_HPP
#define NOYA_STATIC_RANGE_INVERSIONS_HPP 1
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(n log n + n sqrt(n)) preprocessing with linear sort
/// workspace, O(sqrt(n)) per query. Space: O(1+n+d sqrt(n)), d distinct values.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Static inversion counts for arbitrary online half-open queries.
/// Counts pairs i < j with a[j] < a[i]; equivalent values are not inversions.
/// Values need only strict weak ordering; bounds assume O(1) comparisons and
/// an int-sized array. The default-constructed object is empty. Rebuilding
/// may retain capacity from earlier builds beyond the stated fresh-build space.
template <class T> class static_range_inversions {
using count_type = std::uint64_t;
struct bucket {
std::vector<int> rk, ord, pf;
std::vector<count_type> pi, bi, pe;
};
int n_ = 0;
int bs_ = 1;
std::vector<bucket> bs;
public:
static_range_inversions() = default;
explicit static_range_inversions(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
n_ = int(a.size());
bs_ = int(std::sqrt(std::max(1, n_))) + 1;
std::vector<int> order(n_);
std::iota(order.begin(), order.end(), 0);
std::stable_sort(order.begin(), order.end(),
[&](int l, int r) { return a[l] < a[r]; });
std::vector<int> rk(n_);
int d = 0;
for (int i = 0; i < n_; ++i) {
if (i == 0 || a[order[i - 1]] < a[order[i]]) ++d;
rk[order[i]] = d - 1;
}
// The final bucket also represents r == n when n is a block multiple.
bs.assign(n_ / bs_ + 1, {});
for (int rb = 0; rb < int(bs.size()); ++rb) {
bucket &cur = bs[rb];
int arr = rb * bs_, len = std::min(bs_, n_ - arr);
cur.rk.assign(rk.begin() + arr, rk.begin() + arr + len);
cur.ord.reserve(len);
cur.pi.resize(len + 1);
cur.pe.resize(len + 1);
cur.bi.resize(rb);
}
// Stable global order also gives each block's sorted position order.
for (int pos : order) bs[pos / bs_].ord.push_back(pos % bs_);
std::vector<int> cnt(d), equal(d);
for (bucket &cur : bs) {
int len = int(cur.rk.size());
cur.pf.resize(std::size_t(d) + 1);
for (int v = 0; v < d; ++v) cur.pf[v + 1] = cur.pf[v] + cnt[v];
for (int v : cur.rk) ++cnt[v];
std::vector<int> local(len), bit(len + 1);
for (int i = 0; i < len; ++i) local[cur.ord[i]] = i;
for (int i = 0; i < len; ++i) {
int less = 0;
for (int p = local[i]; p; p -= p & -p) less += bit[p];
cur.pi[i + 1] = cur.pi[i] + i - less;
for (int p = local[i] + 1; p <= len; p += p & -p) ++bit[p];
cur.pe[i + 1] = cur.pe[i] + equal[cur.rk[i]]++;
}
for (int v : cur.rk) equal[v] = 0;
}
// A new smaller value makes inversions with greater values in left blocks.
// Reverse stable order processes equal values right-to-left, excluding them.
std::vector<int> seen(bs.size());
for (int i = n_; i-- > 0;) {
int rb = order[i] / bs_;
if (rb + 1 < int(bs.size())) {
auto &row = bs[rb + 1].bi;
for (int lb = 0; lb < rb; ++lb) row[lb] += seen[lb];
}
++seen[rb];
}
for (int rb = 0; rb + 1 < int(bs.size()); ++rb) {
auto &row = bs[rb + 1].bi;
count_type inv = bs[rb].pi.back();
row[rb] = inv;
for (int lb = rb; lb-- > 0;) {
inv += row[lb];
row[lb] = bs[rb].bi[lb] + inv;
}
}
}
int size() const { return n_; }
count_type inversions(int arr, int lst) const {
assert(0 <= arr && arr <= lst && lst <= n_);
if (arr == lst) return 0;
int bl = arr / bs_, pl = arr % bs_;
int br = lst / bs_, pr = lst % bs_;
const bucket &l = bs[bl];
const bucket &r = bs[br];
if (bl == br) {
count_type res = l.pi[pr] - l.pi[pl];
if (pl == 0) return res;
int num = 0;
for (int idx : l.ord) {
if (idx < pl) res -= num;
else if (idx < pr) ++num;
}
return res;
}
count_type res = r.bi[bl];
for (int i = 0; i < pl; ++i) res -= r.pf[l.rk[i]] - l.pf[l.rk[i]];
// Strict frequency subtraction also removes increasing pairs inside the
// left prefix. Add them back, excluding inversions and equal pairs.
res += count_type(pl) * (pl - 1) / 2 - l.pi[pl] - l.pe[pl];
res += r.pi[pr];
res += count_type(br - bl) * bs_ * pr;
// A right element forms inversions only with strictly greater left values.
for (int i = 0; i < pr; ++i)
res -= r.pf[r.rk[i] + 1] - l.pf[r.rk[i] + 1];
if (pl == 0 || pr == 0) return res;
int num = 0;
auto ri = r.ord.begin();
for (int idx : l.ord) {
while (ri != r.ord.end() && r.rk[*ri] < l.rk[idx]) {
if (*ri < pr) ++num;
++ri;
}
if (idx < pl) res -= num;
}
return res;
}
};
} // namespace noya
#endif // NOYA_STATIC_RANGE_INVERSIONS_HPP
// SPDX-License-Identifier: Apache-2.0
// Adapted from Library Checker, with changes for libra.
// Sources and license: third_party/README.md.
/// @complexity Time: O(n log n + n sqrt(n)) preprocessing with linear sort
/// workspace, O(sqrt(n)) per query. Space: O(1+n+d sqrt(n)), d distinct values.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Static inversion counts for arbitrary online half-open queries.
/// Counts pairs i < j with a[j] < a[i]; equivalent values are not inversions.
/// Values need only strict weak ordering; bounds assume O(1) comparisons and
/// an int-sized array. The default-constructed object is empty. Rebuilding
/// may retain capacity from earlier builds beyond the stated fresh-build space.
template <class T> class static_range_inversions {
using count_type = std::uint64_t;
struct bucket {
std::vector<int> rk, ord, pf;
std::vector<count_type> pi, bi, pe;
};
int n_ = 0;
int bs_ = 1;
std::vector<bucket> bs;
public:
static_range_inversions() = default;
explicit static_range_inversions(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
n_ = int(a.size());
bs_ = int(std::sqrt(std::max(1, n_))) + 1;
std::vector<int> order(n_);
std::iota(order.begin(), order.end(), 0);
std::stable_sort(order.begin(), order.end(),
[&](int l, int r) { return a[l] < a[r]; });
std::vector<int> rk(n_);
int d = 0;
for (int i = 0; i < n_; ++i) {
if (i == 0 || a[order[i - 1]] < a[order[i]]) ++d;
rk[order[i]] = d - 1;
}
// The final bucket also represents r == n when n is a block multiple.
bs.assign(n_ / bs_ + 1, {});
for (int rb = 0; rb < int(bs.size()); ++rb) {
bucket &cur = bs[rb];
int arr = rb * bs_, len = std::min(bs_, n_ - arr);
cur.rk.assign(rk.begin() + arr, rk.begin() + arr + len);
cur.ord.reserve(len);
cur.pi.resize(len + 1);
cur.pe.resize(len + 1);
cur.bi.resize(rb);
}
// Stable global order also gives each block's sorted position order.
for (int pos : order) bs[pos / bs_].ord.push_back(pos % bs_);
std::vector<int> cnt(d), equal(d);
for (bucket &cur : bs) {
int len = int(cur.rk.size());
cur.pf.resize(std::size_t(d) + 1);
for (int v = 0; v < d; ++v) cur.pf[v + 1] = cur.pf[v] + cnt[v];
for (int v : cur.rk) ++cnt[v];
std::vector<int> local(len), bit(len + 1);
for (int i = 0; i < len; ++i) local[cur.ord[i]] = i;
for (int i = 0; i < len; ++i) {
int less = 0;
for (int p = local[i]; p; p -= p & -p) less += bit[p];
cur.pi[i + 1] = cur.pi[i] + i - less;
for (int p = local[i] + 1; p <= len; p += p & -p) ++bit[p];
cur.pe[i + 1] = cur.pe[i] + equal[cur.rk[i]]++;
}
for (int v : cur.rk) equal[v] = 0;
}
// A new smaller value makes inversions with greater values in left blocks.
// Reverse stable order processes equal values right-to-left, excluding them.
std::vector<int> seen(bs.size());
for (int i = n_; i-- > 0;) {
int rb = order[i] / bs_;
if (rb + 1 < int(bs.size())) {
auto &row = bs[rb + 1].bi;
for (int lb = 0; lb < rb; ++lb) row[lb] += seen[lb];
}
++seen[rb];
}
for (int rb = 0; rb + 1 < int(bs.size()); ++rb) {
auto &row = bs[rb + 1].bi;
count_type inv = bs[rb].pi.back();
row[rb] = inv;
for (int lb = rb; lb-- > 0;) {
inv += row[lb];
row[lb] = bs[rb].bi[lb] + inv;
}
}
}
int size() const { return n_; }
count_type inversions(int arr, int lst) const {
assert(0 <= arr && arr <= lst && lst <= n_);
if (arr == lst) return 0;
int bl = arr / bs_, pl = arr % bs_;
int br = lst / bs_, pr = lst % bs_;
const bucket &l = bs[bl];
const bucket &r = bs[br];
if (bl == br) {
count_type res = l.pi[pr] - l.pi[pl];
if (pl == 0) return res;
int num = 0;
for (int idx : l.ord) {
if (idx < pl) res -= num;
else if (idx < pr) ++num;
}
return res;
}
count_type res = r.bi[bl];
for (int i = 0; i < pl; ++i) res -= r.pf[l.rk[i]] - l.pf[l.rk[i]];
// Strict frequency subtraction also removes increasing pairs inside the
// left prefix. Add them back, excluding inversions and equal pairs.
res += count_type(pl) * (pl - 1) / 2 - l.pi[pl] - l.pe[pl];
res += r.pi[pr];
res += count_type(br - bl) * bs_ * pr;
// A right element forms inversions only with strictly greater left values.
for (int i = 0; i < pr; ++i)
res -= r.pf[r.rk[i] + 1] - l.pf[r.rk[i] + 1];
if (pl == 0 || pr == 0) return res;
int num = 0;
auto ri = r.ord.begin();
for (int idx : l.ord) {
while (ri != r.ord.end() && r.rk[*ri] < l.rk[idx]) {
if (*ri < pr) ++num;
++ri;
}
if (idx < pl) res -= num;
}
return res;
}
};
} // namespace noya
// NOYA_STATIC_RANGE_INVERSIONS_HPP