static_range_inversions.hpp¶
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.
Verified by static_range_inversions_query.
预处理后回答静态数组任意区间的逆序对数量；适合大量子数组排序混乱度查询。
Implementation¶
#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> rank;
std::vector<int> sorted_indices;
std::vector<count_type> prefix_inversions;
std::vector<count_type> block_inversions;
std::vector<int> prefix_frequency;
};
int n_ = 0;
int block_size_ = 1;
std::vector<bucket> buckets_;
public:
static_range_inversions() = default;
explicit static_range_inversions(const std::vector<T> &values) {
build(values);
}
void build(const std::vector<T> &values) {
n_ = int(values.size());
block_size_ = 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 left, int right) {
return values[left] < values[right];
});
std::vector<int> rank(n_);
for (int i = 0; i < n_; i++) {
rank[order[i]] = i;
}
buckets_.assign(n_ / block_size_ + 1, {});
std::vector<int> frequency(n_);
for (int right_block = 0; right_block < int(buckets_.size());
right_block++) {
bucket ¤t = buckets_[right_block];
int first = right_block * block_size_;
int last = std::min(n_, first + block_size_);
current.rank.assign(rank.begin() + first, rank.begin() + last);
int length = int(current.rank.size());
current.sorted_indices.resize(length);
std::iota(current.sorted_indices.begin(), current.sorted_indices.end(),
0);
std::sort(current.sorted_indices.begin(), current.sorted_indices.end(),
[&](int left, int right) {
return current.rank[left] < current.rank[right];
});
current.prefix_frequency.resize(n_ + 1);
for (int value = 0; value < n_; value++) {
current.prefix_frequency[value + 1] =
current.prefix_frequency[value] + frequency[value];
}
for (int value : current.rank) {
frequency[value]++;
}
current.prefix_inversions.resize(length);
count_type inversions = 0;
for (int i = 0; i < length; i++) {
current.prefix_inversions[i] = inversions;
for (int j = 0; j < i; j++) {
inversions += current.rank[j] > current.rank[i];
}
}
if (right_block + 1 == int(buckets_.size())) {
current.prefix_inversions.push_back(inversions);
continue;
}
buckets_[right_block + 1].block_inversions.resize(right_block + 1);
buckets_[right_block + 1].block_inversions[right_block] = inversions;
for (int left_block = right_block - 1; left_block >= 0; left_block--) {
const bucket &left = buckets_[left_block];
int right_index = 0;
for (int index : left.sorted_indices) {
while (right_index < int(current.sorted_indices.size()) &&
current.rank[current.sorted_indices[right_index]] <
left.rank[index]) {
right_index++;
}
inversions += right_index;
}
buckets_[right_block + 1].block_inversions[left_block] =
current.block_inversions[left_block] + inversions;
}
}
}
int size() const { return n_; }
count_type inversions(int first, int last) const {
int first_block = first / block_size_;
int first_remainder = first % block_size_;
int last_block = last / block_size_;
int last_remainder = last % block_size_;
const bucket &left = buckets_[first_block];
const bucket &right = buckets_[last_block];
if (first_block == last_block) {
count_type result = left.prefix_inversions[last_remainder] -
left.prefix_inversions[first_remainder];
int included = 0;
for (int index : left.sorted_indices) {
if (index < first_remainder) {
result -= included;
} else if (index < last_remainder) {
included++;
}
}
return result;
}
count_type result = right.block_inversions[first_block];
for (int i = 0; i < first_remainder; i++) {
result -= right.prefix_frequency[left.rank[i]] -
left.prefix_frequency[left.rank[i]];
}
result += count_type(first_remainder) * (first_remainder - 1) / 2;
result -= left.prefix_inversions[first_remainder];
result += right.prefix_inversions[last_remainder];
result += count_type(last_block - first_block) * block_size_ *
last_remainder;
for (int i = 0; i < last_remainder; i++) {
result -= right.prefix_frequency[right.rank[i]] -
left.prefix_frequency[right.rank[i]];
}
int included = 0;
auto right_it = right.sorted_indices.begin();
for (int index : left.sorted_indices) {
while (right_it != right.sorted_indices.end() &&
right.rank[*right_it] < left.rank[index]) {
if (*right_it < last_remainder) {
included++;
}
++right_it;
}
if (index < first_remainder) {
result -= included;
}
}
return result;
}
};
} // 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> rank;
std::vector<int> sorted_indices;
std::vector<count_type> prefix_inversions;
std::vector<count_type> block_inversions;
std::vector<int> prefix_frequency;
};
int n_ = 0;
int block_size_ = 1;
std::vector<bucket> buckets_;
public:
static_range_inversions() = default;
explicit static_range_inversions(const std::vector<T> &values) {
build(values);
}
void build(const std::vector<T> &values) {
n_ = int(values.size());
block_size_ = 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 left, int right) {
return values[left] < values[right];
});
std::vector<int> rank(n_);
for (int i = 0; i < n_; i++) {
rank[order[i]] = i;
}
buckets_.assign(n_ / block_size_ + 1, {});
std::vector<int> frequency(n_);
for (int right_block = 0; right_block < int(buckets_.size());
right_block++) {
bucket ¤t = buckets_[right_block];
int first = right_block * block_size_;
int last = std::min(n_, first + block_size_);
current.rank.assign(rank.begin() + first, rank.begin() + last);
int length = int(current.rank.size());
current.sorted_indices.resize(length);
std::iota(current.sorted_indices.begin(), current.sorted_indices.end(),
0);
std::sort(current.sorted_indices.begin(), current.sorted_indices.end(),
[&](int left, int right) {
return current.rank[left] < current.rank[right];
});
current.prefix_frequency.resize(n_ + 1);
for (int value = 0; value < n_; value++) {
current.prefix_frequency[value + 1] =
current.prefix_frequency[value] + frequency[value];
}
for (int value : current.rank) {
frequency[value]++;
}
current.prefix_inversions.resize(length);
count_type inversions = 0;
for (int i = 0; i < length; i++) {
current.prefix_inversions[i] = inversions;
for (int j = 0; j < i; j++) {
inversions += current.rank[j] > current.rank[i];
}
}
if (right_block + 1 == int(buckets_.size())) {
current.prefix_inversions.push_back(inversions);
continue;
}
buckets_[right_block + 1].block_inversions.resize(right_block + 1);
buckets_[right_block + 1].block_inversions[right_block] = inversions;
for (int left_block = right_block - 1; left_block >= 0; left_block--) {
const bucket &left = buckets_[left_block];
int right_index = 0;
for (int index : left.sorted_indices) {
while (right_index < int(current.sorted_indices.size()) &&
current.rank[current.sorted_indices[right_index]] <
left.rank[index]) {
right_index++;
}
inversions += right_index;
}
buckets_[right_block + 1].block_inversions[left_block] =
current.block_inversions[left_block] + inversions;
}
}
}
int size() const { return n_; }
count_type inversions(int first, int last) const {
int first_block = first / block_size_;
int first_remainder = first % block_size_;
int last_block = last / block_size_;
int last_remainder = last % block_size_;
const bucket &left = buckets_[first_block];
const bucket &right = buckets_[last_block];
if (first_block == last_block) {
count_type result = left.prefix_inversions[last_remainder] -
left.prefix_inversions[first_remainder];
int included = 0;
for (int index : left.sorted_indices) {
if (index < first_remainder) {
result -= included;
} else if (index < last_remainder) {
included++;
}
}
return result;
}
count_type result = right.block_inversions[first_block];
for (int i = 0; i < first_remainder; i++) {
result -= right.prefix_frequency[left.rank[i]] -
left.prefix_frequency[left.rank[i]];
}
result += count_type(first_remainder) * (first_remainder - 1) / 2;
result -= left.prefix_inversions[first_remainder];
result += right.prefix_inversions[last_remainder];
result += count_type(last_block - first_block) * block_size_ *
last_remainder;
for (int i = 0; i < last_remainder; i++) {
result -= right.prefix_frequency[right.rank[i]] -
left.prefix_frequency[right.rank[i]];
}
int included = 0;
auto right_it = right.sorted_indices.begin();
for (int index : left.sorted_indices) {
while (right_it != right.sorted_indices.end() &&
right.rank[*right_it] < left.rank[index]) {
if (*right_it < last_remainder) {
included++;
}
++right_it;
}
if (index < first_remainder) {
result -= included;
}
}
return result;
}
};
} // namespace noya