cdq_dominance.hpp¶
For each 3D point, count input points coordinate-wise no greater than it, including itself and duplicate copies, in O(n log^2 n).
用 CDQ 分治统计多维偏序贡献；适合二维/三维点对计数、前缀转移和带时间顺序的离线问题。
Implementation¶
#ifndef NOYA_CDQ_DOMINANCE_HPP
#define NOYA_CDQ_DOMINANCE_HPP 1
/// @complexity Time: O(n log^2 n).
/// Space: O(n).
#include <algorithm>
#include <array>
#include <cstdint>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
/// @brief For each 3D point, count input points coordinate-wise no greater than
/// it, including itself and duplicate copies, in O(n log^2 n).
template <class T>
std::vector<std::int64_t>
dominance_count_3d(const std::vector<std::array<T, 3>> &points) {
struct item {
T x;
T y;
T z;
int z_rank = 0;
std::int64_t multiplicity = 0;
std::int64_t answer = 0;
std::vector<int> ids;
};
std::vector<int> order(points.size());
for (int index = 0; index < int(points.size()); index++) {
order[index] = index;
}
std::sort(order.begin(), order.end(), [&](int first, int second) {
return points[first] < points[second];
});
std::vector<item> items;
for (int id : order) {
auto [x, y, z] = points[id];
if (items.empty() || std::tie(items.back().x, items.back().y,
items.back().z) != std::tie(x, y, z)) {
items.push_back({x, y, z});
}
items.back().multiplicity++;
items.back().ids.push_back(id);
}
std::vector<T> z_values;
for (const item &value : items) {
z_values.push_back(value.z);
}
std::sort(z_values.begin(), z_values.end());
z_values.erase(std::unique(z_values.begin(), z_values.end()), z_values.end());
for (item &value : items) {
value.z_rank =
int(std::lower_bound(z_values.begin(), z_values.end(), value.z) -
z_values.begin());
value.answer = value.multiplicity;
}
std::vector<std::int64_t> fenwick(z_values.size() + 1);
auto add = [&](int position, std::int64_t delta) {
for (position++; position < int(fenwick.size());
position += position & -position) {
fenwick[position] += delta;
}
};
auto prefix = [&](int right) {
std::int64_t result = 0;
for (; right > 0; right -= right & -right) {
result += fenwick[right];
}
return result;
};
std::vector<item> buffer(items.size());
auto solve = [&](auto &self, int left, int right) -> void {
if (right - left <= 1) {
return;
}
int middle = std::midpoint(left, right);
self(self, left, middle);
self(self, middle, right);
int first = left;
for (int second = middle; second < right; second++) {
while (first < middle && !(items[second].y < items[first].y)) {
add(items[first].z_rank, items[first].multiplicity);
first++;
}
items[second].answer += prefix(items[second].z_rank + 1);
}
for (int index = left; index < first; index++) {
add(items[index].z_rank, -items[index].multiplicity);
}
std::merge(items.begin() + left, items.begin() + middle,
items.begin() + middle, items.begin() + right,
buffer.begin() + left, [](const item &a, const item &b) {
return std::tie(a.y, a.z) < std::tie(b.y, b.z);
});
std::move(buffer.begin() + left, buffer.begin() + right,
items.begin() + left);
};
solve(solve, 0, int(items.size()));
std::vector<std::int64_t> result(points.size());
for (const item &value : items) {
for (int id : value.ids) {
result[id] = value.answer;
}
}
return result;
}
} // namespace noya
#endif // NOYA_CDQ_DOMINANCE_HPP
#include <algorithm>
#include <array>
#include <cstdint>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>
/// @complexity Time: O(n log^2 n).
/// Space: O(n).
namespace noya {
/// @brief For each 3D point, count input points coordinate-wise no greater than
/// it, including itself and duplicate copies, in O(n log^2 n).
template <class T>
std::vector<std::int64_t>
dominance_count_3d(const std::vector<std::array<T, 3>> &points) {
struct item {
T x;
T y;
T z;
int z_rank = 0;
std::int64_t multiplicity = 0;
std::int64_t answer = 0;
std::vector<int> ids;
};
std::vector<int> order(points.size());
for (int index = 0; index < int(points.size()); index++) {
order[index] = index;
}
std::sort(order.begin(), order.end(), [&](int first, int second) {
return points[first] < points[second];
});
std::vector<item> items;
for (int id : order) {
auto [x, y, z] = points[id];
if (items.empty() || std::tie(items.back().x, items.back().y,
items.back().z) != std::tie(x, y, z)) {
items.push_back({x, y, z});
}
items.back().multiplicity++;
items.back().ids.push_back(id);
}
std::vector<T> z_values;
for (const item &value : items) {
z_values.push_back(value.z);
}
std::sort(z_values.begin(), z_values.end());
z_values.erase(std::unique(z_values.begin(), z_values.end()), z_values.end());
for (item &value : items) {
value.z_rank =
int(std::lower_bound(z_values.begin(), z_values.end(), value.z) -
z_values.begin());
value.answer = value.multiplicity;
}
std::vector<std::int64_t> fenwick(z_values.size() + 1);
auto add = [&](int position, std::int64_t delta) {
for (position++; position < int(fenwick.size());
position += position & -position) {
fenwick[position] += delta;
}
};
auto prefix = [&](int right) {
std::int64_t result = 0;
for (; right > 0; right -= right & -right) {
result += fenwick[right];
}
return result;
};
std::vector<item> buffer(items.size());
auto solve = [&](auto &self, int left, int right) -> void {
if (right - left <= 1) {
return;
}
int middle = std::midpoint(left, right);
self(self, left, middle);
self(self, middle, right);
int first = left;
for (int second = middle; second < right; second++) {
while (first < middle && !(items[second].y < items[first].y)) {
add(items[first].z_rank, items[first].multiplicity);
first++;
}
items[second].answer += prefix(items[second].z_rank + 1);
}
for (int index = left; index < first; index++) {
add(items[index].z_rank, -items[index].multiplicity);
}
std::merge(items.begin() + left, items.begin() + middle,
items.begin() + middle, items.begin() + right,
buffer.begin() + left, [](const item &a, const item &b) {
return std::tie(a.y, a.z) < std::tie(b.y, b.z);
});
std::move(buffer.begin() + left, buffer.begin() + right,
items.begin() + left);
};
solve(solve, 0, int(items.size()));
std::vector<std::int64_t> result(points.size());
for (const item &value : items) {
for (int id : value.ids) {
result[id] = value.answer;
}
}
return result;
}
} // namespace noya