cdq_dominance.hpp¶
用 CDQ 分治统计多维偏序贡献；适合二维/三维点对计数、前缀转移和带时间顺序的离线问题。
Complexity: Time: O(n log^2 n). Space: O(n).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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>> &pt) {
struct item {
T x;
T y;
T z;
int zr = 0;
std::int64_t cnt = 0;
std::int64_t ans = 0;
std::vector<int> ids;
};
std::vector<int> ord(pt.size());
for (int idx = 0; idx < int(pt.size()); idx++) {
ord[idx] = idx;
}
std::sort(ord.begin(), ord.end(),
[&](int arr, int B) { return pt[arr] < pt[B]; });
std::vector<item> pts;
for (int id : ord) {
auto [x, y, z] = pt[id];
if (pts.empty() || std::tie(pts.back().x, pts.back().y, pts.back().z) !=
std::tie(x, y, z)) {
pts.push_back({x, y, z});
}
pts.back().cnt++;
pts.back().ids.push_back(id);
}
std::vector<T> zs;
for (const item &val : pts) {
zs.push_back(val.z);
}
std::sort(zs.begin(), zs.end());
zs.erase(std::unique(zs.begin(), zs.end()), zs.end());
for (item &val : pts) {
val.zr = int(std::lower_bound(zs.begin(), zs.end(), val.z) - zs.begin());
val.ans = val.cnt;
}
std::vector<std::int64_t> bit(zs.size() + 1);
auto add = [&](int pos, std::int64_t dif) {
for (pos++; pos < int(bit.size()); pos += pos & -pos) {
bit[pos] += dif;
}
};
auto pre = [&](int r) {
std::int64_t res = 0;
for (; r > 0; r -= r & -r) {
res += bit[r];
}
return res;
};
std::vector<item> buf(pts.size());
auto dfs = [&](auto &f, int l, int r) -> void {
if (r - l <= 1) {
return;
}
int mid = std::midpoint(l, r);
f(f, l, mid);
f(f, mid, r);
int arr = l;
for (int B = mid; B < r; B++) {
while (arr < mid && !(pts[B].y < pts[arr].y)) {
add(pts[arr].zr, pts[arr].cnt);
arr++;
}
pts[B].ans += pre(pts[B].zr + 1);
}
for (int idx = l; idx < arr; idx++) {
add(pts[idx].zr, -pts[idx].cnt);
}
std::merge(pts.begin() + l, pts.begin() + mid, pts.begin() + mid,
pts.begin() + r, buf.begin() + l,
[](const item &a, const item &b) {
return std::tie(a.y, a.z) < std::tie(b.y, b.z);
});
std::move(buf.begin() + l, buf.begin() + r, pts.begin() + l);
};
dfs(dfs, 0, int(pts.size()));
std::vector<std::int64_t> res(pt.size());
for (const item &val : pts) {
for (int id : val.ids) {
res[id] = val.ans;
}
}
return res;
}
} // namespace noya
#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>> &pt) {
struct item {
T x;
T y;
T z;
int zr = 0;
std::int64_t cnt = 0;
std::int64_t ans = 0;
std::vector<int> ids;
};
std::vector<int> ord(pt.size());
for (int idx = 0; idx < int(pt.size()); idx++) {
ord[idx] = idx;
}
std::sort(ord.begin(), ord.end(),
[&](int arr, int B) { return pt[arr] < pt[B]; });
std::vector<item> pts;
for (int id : ord) {
auto [x, y, z] = pt[id];
if (pts.empty() || std::tie(pts.back().x, pts.back().y, pts.back().z) !=
std::tie(x, y, z)) {
pts.push_back({x, y, z});
}
pts.back().cnt++;
pts.back().ids.push_back(id);
}
std::vector<T> zs;
for (const item &val : pts) {
zs.push_back(val.z);
}
std::sort(zs.begin(), zs.end());
zs.erase(std::unique(zs.begin(), zs.end()), zs.end());
for (item &val : pts) {
val.zr = int(std::lower_bound(zs.begin(), zs.end(), val.z) - zs.begin());
val.ans = val.cnt;
}
std::vector<std::int64_t> bit(zs.size() + 1);
auto add = [&](int pos, std::int64_t dif) {
for (pos++; pos < int(bit.size()); pos += pos & -pos) {
bit[pos] += dif;
}
};
auto pre = [&](int r) {
std::int64_t res = 0;
for (; r > 0; r -= r & -r) {
res += bit[r];
}
return res;
};
std::vector<item> buf(pts.size());
auto dfs = [&](auto &f, int l, int r) -> void {
if (r - l <= 1) {
return;
}
int mid = std::midpoint(l, r);
f(f, l, mid);
f(f, mid, r);
int arr = l;
for (int B = mid; B < r; B++) {
while (arr < mid && !(pts[B].y < pts[arr].y)) {
add(pts[arr].zr, pts[arr].cnt);
arr++;
}
pts[B].ans += pre(pts[B].zr + 1);
}
for (int idx = l; idx < arr; idx++) {
add(pts[idx].zr, -pts[idx].cnt);
}
std::merge(pts.begin() + l, pts.begin() + mid, pts.begin() + mid,
pts.begin() + r, buf.begin() + l,
[](const item &a, const item &b) {
return std::tie(a.y, a.z) < std::tie(b.y, b.z);
});
std::move(buf.begin() + l, buf.begin() + r, pts.begin() + l);
};
dfs(dfs, 0, int(pts.size()));
std::vector<std::int64_t> res(pt.size());
for (const item &val : pts) {
for (int id : val.ids) {
res[id] = val.ans;
}
}
return res;
}
} // 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>> &pt) {
struct item {
T x;
T y;
T z;
int zr = 0;
std::int64_t cnt = 0;
std::int64_t ans = 0;
std::vector<int> ids;
};
std::vector<int> ord(pt.size());
for (int idx = 0; idx < int(pt.size()); idx++) {
ord[idx] = idx;
}
std::sort(ord.begin(), ord.end(),
[&](int arr, int B) { return pt[arr] < pt[B]; });
std::vector<item> pts;
for (int id : ord) {
auto [x, y, z] = pt[id];
if (pts.empty() || std::tie(pts.back().x, pts.back().y, pts.back().z) !=
std::tie(x, y, z)) {
pts.push_back({x, y, z});
}
pts.back().cnt++;
pts.back().ids.push_back(id);
}
std::vector<T> zs;
for (const item &val : pts) {
zs.push_back(val.z);
}
std::sort(zs.begin(), zs.end());
zs.erase(std::unique(zs.begin(), zs.end()), zs.end());
for (item &val : pts) {
val.zr = int(std::lower_bound(zs.begin(), zs.end(), val.z) - zs.begin());
val.ans = val.cnt;
}
std::vector<std::int64_t> bit(zs.size() + 1);
auto add = [&](int pos, std::int64_t dif) {
for (pos++; pos < int(bit.size()); pos += pos & -pos) {
bit[pos] += dif;
}
};
auto pre = [&](int r) {
std::int64_t res = 0;
for (; r > 0; r -= r & -r) {
res += bit[r];
}
return res;
};
std::vector<item> buf(pts.size());
auto dfs = [&](auto &f, int l, int r) -> void {
if (r - l <= 1) {
return;
}
int mid = std::midpoint(l, r);
f(f, l, mid);
f(f, mid, r);
int arr = l;
for (int B = mid; B < r; B++) {
while (arr < mid && !(pts[B].y < pts[arr].y)) {
add(pts[arr].zr, pts[arr].cnt);
arr++;
}
pts[B].ans += pre(pts[B].zr + 1);
}
for (int idx = l; idx < arr; idx++) {
add(pts[idx].zr, -pts[idx].cnt);
}
std::merge(pts.begin() + l, pts.begin() + mid, pts.begin() + mid,
pts.begin() + r, buf.begin() + l,
[](const item &a, const item &b) {
return std::tie(a.y, a.z) < std::tie(b.y, b.z);
});
std::move(buf.begin() + l, buf.begin() + r, pts.begin() + l);
};
dfs(dfs, 0, int(pts.size()));
std::vector<std::int64_t> res(pt.size());
for (const item &val : pts) {
for (int id : val.ids) {
res[id] = val.ans;
}
}
return res;
}
} // namespace noya