static_range_inversions.hpp¶
预处理后回答静态数组任意区间的逆序对数量；适合大量子数组排序混乱度查询。
Complexity: Time: O(n sqrt(n) log n) preprocessing and O(sqrt(n)) per query. Space: O(n sqrt(n)).
AC 记录：static_range_inversions_query。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n sqrt(n) log n) preprocessing and O(sqrt(n)) per
/// query.
/// Space: O(n sqrt(n)).
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Static range inversion counter. The array is split into square-root
/// blocks. Inversions between every contiguous block interval are
/// precomputed, while sorted block orders and prefix frequencies account for
/// the two partial boundary blocks of a query.
template <class T> class static_range_inversions {
using count_type = std::uint64_t;
struct bucket {
std::vector<int> rk;
std::vector<int> ord;
std::vector<count_type> pi;
std::vector<count_type> bi;
std::vector<int> pf;
};
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> or0(n_);
std::iota(or0.begin(), or0.end(), 0);
std::stable_sort(or0.begin(), or0.end(),
[&](int l, int r) { return a[l] < a[r]; });
std::vector<int> rk(n_);
for (int i = 0; i < n_; i++) {
rk[or0[i]] = i;
}
bs.assign(n_ / bs_ + 1, {});
std::vector<int> cnt(n_);
for (int rb = 0; rb < int(bs.size()); rb++) {
bucket &cur = bs[rb];
int arr = rb * bs_;
int lst = std::min(n_, arr + bs_);
cur.rk.assign(rk.begin() + arr, rk.begin() + lst);
int len = int(cur.rk.size());
cur.ord.resize(len);
std::iota(cur.ord.begin(), cur.ord.end(), 0);
std::sort(cur.ord.begin(), cur.ord.end(),
[&](int l, int r) { return cur.rk[l] < cur.rk[r]; });
cur.pf.resize(n_ + 1);
for (int val = 0; val < n_; val++) {
cur.pf[val + 1] = cur.pf[val] + cnt[val];
}
for (int val : cur.rk) {
cnt[val]++;
}
cur.pi.resize(len);
count_type inv = 0;
for (int i = 0; i < len; i++) {
cur.pi[i] = inv;
for (int j = 0; j < i; j++) {
inv += cur.rk[j] > cur.rk[i];
}
}
if (rb + 1 == int(bs.size())) {
cur.pi.push_back(inv);
continue;
}
bs[rb + 1].bi.resize(rb + 1);
bs[rb + 1].bi[rb] = inv;
for (int lb = rb - 1; lb >= 0; lb--) {
const bucket &l = bs[lb];
int ri = 0;
for (int idx : l.ord) {
while (ri < int(cur.ord.size()) && cur.rk[cur.ord[ri]] < l.rk[idx]) {
ri++;
}
inv += ri;
}
bs[rb + 1].bi[lb] = cur.bi[lb] + inv;
}
}
}
int size() const { return n_; }
count_type inversions(int arr, int lst) const {
int bl = arr / bs_;
int pl = arr % bs_;
int br = lst / bs_;
int 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];
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]];
}
res += count_type(pl) * (pl - 1) / 2;
res -= l.pi[pl];
res += r.pi[pr];
res += count_type(br - bl) * bs_ * pr;
for (int i = 0; i < pr; i++) {
res -= r.pf[r.rk[i]] - l.pf[r.rk[i]];
}
int num = 0;
auto ri0 = r.ord.begin();
for (int idx : l.ord) {
while (ri0 != r.ord.end() && r.rk[*ri0] < l.rk[idx]) {
if (*ri0 < pr) {
num++;
}
++ri0;
}
if (idx < pl) {
res -= num;
}
}
return res;
}
};
} // namespace noya
#ifndef NOYA_STATIC_RANGE_INVERSIONS_HPP
#define NOYA_STATIC_RANGE_INVERSIONS_HPP 1
/// @complexity Time: O(n sqrt(n) log n) preprocessing and O(sqrt(n)) per
/// query.
/// Space: O(n sqrt(n)).
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Static range inversion counter. The array is split into square-root
/// blocks. Inversions between every contiguous block interval are
/// precomputed, while sorted block orders and prefix frequencies account for
/// the two partial boundary blocks of a query.
template <class T> class static_range_inversions {
using count_type = std::uint64_t;
struct bucket {
std::vector<int> rk;
std::vector<int> ord;
std::vector<count_type> pi;
std::vector<count_type> bi;
std::vector<int> pf;
};
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> or0(n_);
std::iota(or0.begin(), or0.end(), 0);
std::stable_sort(or0.begin(), or0.end(),
[&](int l, int r) { return a[l] < a[r]; });
std::vector<int> rk(n_);
for (int i = 0; i < n_; i++) {
rk[or0[i]] = i;
}
bs.assign(n_ / bs_ + 1, {});
std::vector<int> cnt(n_);
for (int rb = 0; rb < int(bs.size()); rb++) {
bucket &cur = bs[rb];
int arr = rb * bs_;
int lst = std::min(n_, arr + bs_);
cur.rk.assign(rk.begin() + arr, rk.begin() + lst);
int len = int(cur.rk.size());
cur.ord.resize(len);
std::iota(cur.ord.begin(), cur.ord.end(), 0);
std::sort(cur.ord.begin(), cur.ord.end(),
[&](int l, int r) { return cur.rk[l] < cur.rk[r]; });
cur.pf.resize(n_ + 1);
for (int val = 0; val < n_; val++) {
cur.pf[val + 1] = cur.pf[val] + cnt[val];
}
for (int val : cur.rk) {
cnt[val]++;
}
cur.pi.resize(len);
count_type inv = 0;
for (int i = 0; i < len; i++) {
cur.pi[i] = inv;
for (int j = 0; j < i; j++) {
inv += cur.rk[j] > cur.rk[i];
}
}
if (rb + 1 == int(bs.size())) {
cur.pi.push_back(inv);
continue;
}
bs[rb + 1].bi.resize(rb + 1);
bs[rb + 1].bi[rb] = inv;
for (int lb = rb - 1; lb >= 0; lb--) {
const bucket &l = bs[lb];
int ri = 0;
for (int idx : l.ord) {
while (ri < int(cur.ord.size()) && cur.rk[cur.ord[ri]] < l.rk[idx]) {
ri++;
}
inv += ri;
}
bs[rb + 1].bi[lb] = cur.bi[lb] + inv;
}
}
}
int size() const { return n_; }
count_type inversions(int arr, int lst) const {
int bl = arr / bs_;
int pl = arr % bs_;
int br = lst / bs_;
int 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];
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]];
}
res += count_type(pl) * (pl - 1) / 2;
res -= l.pi[pl];
res += r.pi[pr];
res += count_type(br - bl) * bs_ * pr;
for (int i = 0; i < pr; i++) {
res -= r.pf[r.rk[i]] - l.pf[r.rk[i]];
}
int num = 0;
auto ri0 = r.ord.begin();
for (int idx : l.ord) {
while (ri0 != r.ord.end() && r.rk[*ri0] < l.rk[idx]) {
if (*ri0 < pr) {
num++;
}
++ri0;
}
if (idx < pl) {
res -= num;
}
}
return res;
}
};
} // namespace noya
#endif // NOYA_STATIC_RANGE_INVERSIONS_HPP
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <numeric>
#include <vector>
/// @complexity Time: O(n sqrt(n) log n) preprocessing and O(sqrt(n)) per
/// query.
/// Space: O(n sqrt(n)).
namespace noya {
/// @brief Static range inversion counter. The array is split into square-root
/// blocks. Inversions between every contiguous block interval are
/// precomputed, while sorted block orders and prefix frequencies account for
/// the two partial boundary blocks of a query.
template <class T> class static_range_inversions {
using count_type = std::uint64_t;
struct bucket {
std::vector<int> rk;
std::vector<int> ord;
std::vector<count_type> pi;
std::vector<count_type> bi;
std::vector<int> pf;
};
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> or0(n_);
std::iota(or0.begin(), or0.end(), 0);
std::stable_sort(or0.begin(), or0.end(),
[&](int l, int r) { return a[l] < a[r]; });
std::vector<int> rk(n_);
for (int i = 0; i < n_; i++) {
rk[or0[i]] = i;
}
bs.assign(n_ / bs_ + 1, {});
std::vector<int> cnt(n_);
for (int rb = 0; rb < int(bs.size()); rb++) {
bucket &cur = bs[rb];
int arr = rb * bs_;
int lst = std::min(n_, arr + bs_);
cur.rk.assign(rk.begin() + arr, rk.begin() + lst);
int len = int(cur.rk.size());
cur.ord.resize(len);
std::iota(cur.ord.begin(), cur.ord.end(), 0);
std::sort(cur.ord.begin(), cur.ord.end(),
[&](int l, int r) { return cur.rk[l] < cur.rk[r]; });
cur.pf.resize(n_ + 1);
for (int val = 0; val < n_; val++) {
cur.pf[val + 1] = cur.pf[val] + cnt[val];
}
for (int val : cur.rk) {
cnt[val]++;
}
cur.pi.resize(len);
count_type inv = 0;
for (int i = 0; i < len; i++) {
cur.pi[i] = inv;
for (int j = 0; j < i; j++) {
inv += cur.rk[j] > cur.rk[i];
}
}
if (rb + 1 == int(bs.size())) {
cur.pi.push_back(inv);
continue;
}
bs[rb + 1].bi.resize(rb + 1);
bs[rb + 1].bi[rb] = inv;
for (int lb = rb - 1; lb >= 0; lb--) {
const bucket &l = bs[lb];
int ri = 0;
for (int idx : l.ord) {
while (ri < int(cur.ord.size()) && cur.rk[cur.ord[ri]] < l.rk[idx]) {
ri++;
}
inv += ri;
}
bs[rb + 1].bi[lb] = cur.bi[lb] + inv;
}
}
}
int size() const { return n_; }
count_type inversions(int arr, int lst) const {
int bl = arr / bs_;
int pl = arr % bs_;
int br = lst / bs_;
int 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];
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]];
}
res += count_type(pl) * (pl - 1) / 2;
res -= l.pi[pl];
res += r.pi[pr];
res += count_type(br - bl) * bs_ * pr;
for (int i = 0; i < pr; i++) {
res -= r.pf[r.rk[i]] - l.pf[r.rk[i]];
}
int num = 0;
auto ri0 = r.ord.begin();
for (int idx : l.ord) {
while (ri0 != r.ord.end() && r.rk[*ri0] < l.rk[idx]) {
if (*ri0 < pr) {
num++;
}
++ri0;
}
if (idx < pl) {
res -= num;
}
}
return res;
}
};
} // namespace noya