This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/graph/manhattan_minimum_distances.hpp"
$N$ 個の点 $(x_i,y_i)$ が与えられるので,以下で定まる $d _ i$ を全ての $i$ に対して $O(N\log N)$ 時間で計算する.
#ifndef SUISEN_MANHATTAN_MINIMUM_DISTANCES #define SUISEN_MANHATTAN_MINIMUM_DISTANCES #include <algorithm> #include <limits> #include <numeric> #include <vector> #include "library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp" namespace suisen { namespace internal::manhattan_minimum_distances { template <typename T> T op(T x, T y) { return std::max(x, y); }; template <typename T> T e() { return std::numeric_limits<T>::min(); }; template <typename T> using PrefixMaxQuery = FenwickTreePrefix<T, op<T>, e<T>>; } // namespace internal::manhattan_minimum_distances template <typename T> std::vector<T> manhattan_minimum_distances(std::vector<std::pair<T, T>> points) { using namespace internal::manhattan_minimum_distances; const int n = points.size(); std::vector<int> p(n); std::iota(p.begin(), p.end(), 0); std::vector<T> res(n, std::numeric_limits<T>::max()); auto sweep = [&] { std::sort( p.begin(), p.end(), [&points](int i, int j) { const auto &[xi, yi] = points[i]; const auto &[xj, yj] = points[j]; return yi - xi == yj - xj ? xi < xj : yi - xi < yj - xj; } ); std::vector<T> comp_x(n); for (int i = 0; i < n; ++i) comp_x[i] = points[i].first; std::sort(comp_x.begin(), comp_x.end()); comp_x.erase(std::unique(comp_x.begin(), comp_x.end()), comp_x.end()); const int m = comp_x.size(); auto compress = [&](const T& x) { return std::lower_bound(comp_x.begin(), comp_x.end(), x) - comp_x.begin(); }; PrefixMaxQuery<T> pmq(m); for (int i : p) { const auto& [x, y] = points[i]; const int cx = compress(x); if (const auto v = pmq.prefix_query(cx + 1); v != e<T>()) { res[i] = std::min(res[i], x + y - v); } pmq.apply(cx, x + y); } }; for (int x_rev = 0; x_rev < 2; ++x_rev) { for (int y_rev = 0; y_rev < 2; ++y_rev) { for (int xy_rev = 0; xy_rev < 2; ++xy_rev) { sweep(); for (auto& [x, y] : points) std::swap(x, y); } for (auto& [x, _] : points) x = -x; } for (auto& [_, y] : points) y = -y; } return res; } } // namespace suisen #endif // SUISEN_MANHATTAN_MINIMUM_DISTANCES
#line 1 "library/graph/manhattan_minimum_distances.hpp" #include <algorithm> #include <limits> #include <numeric> #include <vector> #line 1 "library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp" #line 5 "library/datastructure/fenwick_tree/fenwick_tree_prefix.hpp" namespace suisen { template <typename T, T(*op)(T, T), T(*e)()> struct FenwickTreePrefix { FenwickTreePrefix() : FenwickTreePrefix(0) {} explicit FenwickTreePrefix(int n) : _n(n), _dat(_n + 1, e()) {} FenwickTreePrefix(const std::vector<T> &dat) : _n(dat.size()), _dat(_n + 1, e()) { for (int i = _n; i > 0; --i) { _dat[i] = op(_dat[i], dat[i - 1]); if (int p = i + (-i & i); p <= _n) _dat[p] = op(_dat[p], _dat[i]); } } void apply(int i, const T& val) { for (++i; i <= _n; i += -i & i) _dat[i] = op(_dat[i], val); } T prefix_query(int r) const { T res = e(); for (; r; r -= -r & r) res = op(res, _dat[r]); return res; } private: int _n; std::vector<T> _dat; }; } // namespace suisen #line 10 "library/graph/manhattan_minimum_distances.hpp" namespace suisen { namespace internal::manhattan_minimum_distances { template <typename T> T op(T x, T y) { return std::max(x, y); }; template <typename T> T e() { return std::numeric_limits<T>::min(); }; template <typename T> using PrefixMaxQuery = FenwickTreePrefix<T, op<T>, e<T>>; } // namespace internal::manhattan_minimum_distances template <typename T> std::vector<T> manhattan_minimum_distances(std::vector<std::pair<T, T>> points) { using namespace internal::manhattan_minimum_distances; const int n = points.size(); std::vector<int> p(n); std::iota(p.begin(), p.end(), 0); std::vector<T> res(n, std::numeric_limits<T>::max()); auto sweep = [&] { std::sort( p.begin(), p.end(), [&points](int i, int j) { const auto &[xi, yi] = points[i]; const auto &[xj, yj] = points[j]; return yi - xi == yj - xj ? xi < xj : yi - xi < yj - xj; } ); std::vector<T> comp_x(n); for (int i = 0; i < n; ++i) comp_x[i] = points[i].first; std::sort(comp_x.begin(), comp_x.end()); comp_x.erase(std::unique(comp_x.begin(), comp_x.end()), comp_x.end()); const int m = comp_x.size(); auto compress = [&](const T& x) { return std::lower_bound(comp_x.begin(), comp_x.end(), x) - comp_x.begin(); }; PrefixMaxQuery<T> pmq(m); for (int i : p) { const auto& [x, y] = points[i]; const int cx = compress(x); if (const auto v = pmq.prefix_query(cx + 1); v != e<T>()) { res[i] = std::min(res[i], x + y - v); } pmq.apply(cx, x + y); } }; for (int x_rev = 0; x_rev < 2; ++x_rev) { for (int y_rev = 0; y_rev < 2; ++y_rev) { for (int xy_rev = 0; xy_rev < 2; ++xy_rev) { sweep(); for (auto& [x, y] : points) std::swap(x, y); } for (auto& [x, _] : points) x = -x; } for (auto& [_, y] : points) y = -y; } return res; } } // namespace suisen