This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub gyouzasushi/library
#include "graph/manhattan_mst.hpp"
manhattan_mst(x, y)
(u, v, w)
#pragma once #include <algorithm> #include <cassert> #include <iostream> #include <limits> #include <map> #include <numeric> #include <vector> #include "atcoder/segtree.hpp" namespace manhattan_mst_internal { template <typename T> struct S { T val; int id; }; template <typename T> S<T> op(S<T> a, S<T> b) { return a.val < b.val ? a : b; } template <typename T> S<T> e() { return {std::numeric_limits<T>::max(), -1}; } } // namespace manhattan_mst_internal template <typename T> std::vector<std::tuple<int, int, T>> manhattan_mst(std::vector<T> x, std::vector<T> y) { int n = x.size(); assert(int(x.size()) == n && int(y.size()) == n); std::vector<int> id(n); std::iota(id.begin(), id.end(), 0); std::vector<int> y_id(n); std::vector<std::tuple<int, int, T>> ret; for (int a = 0; a < 2; a++) { for (int b = 0; b < 2; b++) { for (int c = 0; c < 2; c++) { sort(id.begin(), id.end(), [&](int i, int j) { if (y[i] - x[i] == y[j] - x[j] && y[i] == y[j]) return i < j; if (y[i] - x[i] == y[j] - x[j]) return y[i] > y[j]; return y[i] - x[i] < y[j] - x[j]; }); std::vector<T> _y = y; std::sort(_y.begin(), _y.end()); for (int i = 0; i < n; i++) { y_id[i] = std::lower_bound(_y.begin(), _y.end(), y[i]) - _y.begin(); } atcoder::segtree<manhattan_mst_internal::S<T>, manhattan_mst_internal::op<T>, manhattan_mst_internal::e<T>> segt(n); for (int i : id) { manhattan_mst_internal::S<T> p = segt.prod(y_id[i], n); if (p.id != -1) { ret.emplace_back(i, p.id, p.val - (x[i] + y[i])); } segt.set(y_id[i], {x[i] + y[i], i}); } std::swap(x, y); } for (T &x : x) x = -x; } for (T &y : y) y = -y; } sort(ret.begin(), ret.end(), [](auto a, auto b) { return std::get<2>(a) < std::get<2>(b); }); return ret; }
#line 2 "graph/manhattan_mst.hpp" #include <algorithm> #include <cassert> #include <iostream> #include <limits> #include <map> #include <numeric> #include <vector> #line 1 "atcoder/segtree.hpp" #line 7 "atcoder/segtree.hpp" #line 1 "atcoder/internal_bit.hpp" #ifdef _MSC_VER #include <intrin.h> #endif namespace atcoder { namespace internal { // @param n `0 <= n` // @return minimum non-negative `x` s.t. `n <= 2**x` int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` constexpr int bsf_constexpr(unsigned int n) { int x = 0; while (!(n & (1 << x))) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal } // namespace atcoder #line 9 "atcoder/segtree.hpp" namespace atcoder { template <class S, S (*op)(S, S), S (*e)()> struct segtree { public: segtree() : segtree(0) {} explicit segtree(int n) : segtree(std::vector<S>(n, e())) {} explicit segtree(const std::vector<S>& v) : _n(int(v.size())) { log = internal::ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) const { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) const { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() const { return d[1]; } template <bool (*f)(S)> int max_right(int l) const { return max_right(l, [](S x) { return f(x); }); } template <class F> int max_right(int l, F f) const { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <bool (*f)(S)> int min_left(int r) const { return min_left(r, [](S x) { return f(x); }); } template <class F> int min_left(int r, F f) const { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<S> d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; } // namespace atcoder #line 11 "graph/manhattan_mst.hpp" namespace manhattan_mst_internal { template <typename T> struct S { T val; int id; }; template <typename T> S<T> op(S<T> a, S<T> b) { return a.val < b.val ? a : b; } template <typename T> S<T> e() { return {std::numeric_limits<T>::max(), -1}; } } // namespace manhattan_mst_internal template <typename T> std::vector<std::tuple<int, int, T>> manhattan_mst(std::vector<T> x, std::vector<T> y) { int n = x.size(); assert(int(x.size()) == n && int(y.size()) == n); std::vector<int> id(n); std::iota(id.begin(), id.end(), 0); std::vector<int> y_id(n); std::vector<std::tuple<int, int, T>> ret; for (int a = 0; a < 2; a++) { for (int b = 0; b < 2; b++) { for (int c = 0; c < 2; c++) { sort(id.begin(), id.end(), [&](int i, int j) { if (y[i] - x[i] == y[j] - x[j] && y[i] == y[j]) return i < j; if (y[i] - x[i] == y[j] - x[j]) return y[i] > y[j]; return y[i] - x[i] < y[j] - x[j]; }); std::vector<T> _y = y; std::sort(_y.begin(), _y.end()); for (int i = 0; i < n; i++) { y_id[i] = std::lower_bound(_y.begin(), _y.end(), y[i]) - _y.begin(); } atcoder::segtree<manhattan_mst_internal::S<T>, manhattan_mst_internal::op<T>, manhattan_mst_internal::e<T>> segt(n); for (int i : id) { manhattan_mst_internal::S<T> p = segt.prod(y_id[i], n); if (p.id != -1) { ret.emplace_back(i, p.id, p.val - (x[i] + y[i])); } segt.set(y_id[i], {x[i] + y[i], i}); } std::swap(x, y); } for (T &x : x) x = -x; } for (T &y : y) y = -y; } sort(ret.begin(), ret.end(), [](auto a, auto b) { return std::get<2>(a) < std::get<2>(b); }); return ret; }