#include #include #include #include #include #include template inline bool chmin(T &lhs, const U &rhs) { if (lhs > rhs) { lhs = rhs; return true; } return false; } template inline bool chmax(T &lhs, const U &rhs) { if (lhs < rhs) { lhs = rhs; return true; } return false; } struct range { using itr = int64_t; struct iterator { itr i; constexpr iterator(itr i_): i(i_) { } constexpr void operator ++ () { ++i; } constexpr itr operator * () const { return i; } constexpr bool operator != (iterator x) const { return i != x.i; } }; const iterator l, r; constexpr range(itr l_, itr r_): l(l_), r(std::max(l_, r_)) { } constexpr iterator begin() const { return l; } constexpr iterator end() const { return r; } }; struct revrange { using itr = int64_t; struct iterator { itr i; constexpr iterator(itr i_): i(i_) { } constexpr void operator ++ () { --i; } constexpr itr operator * () const { return i; } constexpr bool operator != (iterator x) const { return i != x.i; } }; const iterator l, r; constexpr revrange(itr l_, itr r_): l(l_ - 1), r(std::max(l_, r_) - 1) { } constexpr iterator begin() const { return r; } constexpr iterator end() const { return l; } }; template class lazy_propagation_segment_tree { public: using value_type = typename T::value_type; using effector_type = typename T::effector_type; static inline const auto op1 = typename T::value_operation(); static inline const auto op2 = typename T::effector_operation(); static inline const auto op3 = typename T::merge_operation(); private: int size, height; std::vector node; std::vector lazy; value_type fetch(int i, int l) const { if (lazy[i] == op2.identity) return node[i]; return op3(node[i], lazy[i], l); } void apply(int i, int l) { if (lazy[i] == op2.identity) return; if (i < size) { lazy[i << 1 | 0] = op2(lazy[i << 1 | 0], lazy[i]); lazy[i << 1 | 1] = op2(lazy[i << 1 | 1], lazy[i]); } node[i] = op3(node[i], lazy[i], l); lazy[i] = op2.identity; } void update() { for (int i = size - 1; i > 0; --i) { node[i] = op1(node[i << 1 | 0], node[i << 1 | 1]); } } void flush(int i) { for (int k = height; k >= 0; --k) { apply(i >> k, 1 << k); } } void lift(int i) { i >>= 1; int l = 1; while (i > 0) { node[i] = op1(fetch(i << 1 | 0, l), fetch(i << 1 | 1, l)); i >>= 1; l <<= 1; } } public: lazy_propagation_segment_tree() = default; lazy_propagation_segment_tree(int size_, const value_type &initial_ = op1.identity) { init(size_, initial_); } lazy_propagation_segment_tree(const std::vector &node_) { build(node_); } void init(int size_, const value_type &initial_ = op1.identity) { size = 1; height = 0; while (size < size_) { size <<= 1; ++height; } node.assign(size << 1, initial_); lazy.assign(size << 1, op2.identity); update(); } void build(const std::vector &node_) { init(node_.size()); for (int i = 0; i < node_.size(); ++i) { node[i + size] = node_[i]; } update(); } void assign(int i, const value_type &x) { i += size; flush(i); node[i] = x; lift(i); } void modify(int l, int r, const effector_type &x) { if (l >= r) return; flush(l + size); flush(r + size - 1); int tl = l + size, tr = r + size, k = 1; while (tl < tr) { if (tl & 1) { lazy[tl] = op2(lazy[tl], x); apply(tl, k); ++tl; } if (tr & 1) { --tr; lazy[tr] = op2(lazy[tr], x); apply(tr, k); } tl >>= 1; tr >>= 1; k <<= 1; } lift(l + size); lift(r + size - 1); } value_type fold(int l, int r) { if (l >= r) return op1.identity; flush(l + size); flush(r + size - 1); int tl = l + size, tr = r + size, k = 1; value_type resl = op1.identity, resr = op1.identity; while (tl < tr) { if (tl & 1) { apply(tl, k); resl = op1(resl, node[tl]); ++tl; } if (tr & 1) { --tr; apply(tr, k); resr = op1(node[tr], resr); } tl >>= 1; tr >>= 1; k <<= 1; } return op1(resl, resr); } }; template struct range_sum_range_assign { using value_type = std::pair; using effector_type = T; struct value_operation { value_type identity = std::make_pair(0, 0); value_type operator () (const value_type &x, const value_type &y) const { return { x.first + y.first, x.second + y.second }; } }; struct effector_operation { effector_type identity = 0; effector_type operator () (const effector_type, const effector_type &y) const { return y; } }; struct merge_operation { value_type operator () (const value_type &x, const effector_type &y, int) const { return { y * x.second, x.second }; } }; }; template struct range_max_range_assign { using value_type = T; using effector_type = T; struct value_operation { value_type identity = std::numeric_limits::min(); value_type operator () (const value_type &x, const value_type &y) const { return x > y ? x : y; } }; struct effector_operation { effector_type identity = 0; effector_type operator () (const effector_type, const effector_type &y) const { return y; } }; struct merge_operation { value_type operator () (const value_type, const effector_type &y, int) const { return y; } }; }; using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; constexpr i32 inf32 = (i32(1) << 30) - 1; constexpr i64 inf64 = (i64(1) << 62) - 1; std::vector solve(std::vector X, std::vector Y) { size_t N = X.size(); std::vector cmp; cmp.reserve(N + 1); cmp.push_back(0); for (auto x: X) { cmp.push_back(x); } std::sort(cmp.begin(), cmp.end()); cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end()); for (auto &x: X) { x = std::lower_bound(cmp.cbegin(), cmp.cend(), x) - cmp.cbegin() - 1; } size_t xs = cmp.size() - 1; lazy_propagation_segment_tree> sum; lazy_propagation_segment_tree> max(xs); { std::vector> build(xs); for (auto i: range(0, xs)) { build[i].second = cmp[i + 1] - cmp[i]; } sum.build(build); } std::vector res(N); for (auto i: range(0, N)) { auto idx = [&]() -> u32 { if (max.fold(0, X[i] + 1) < Y[i]) { return 0; } if (max.fold(X[i], X[i] + 1) >= Y[i]) { return X[i] + 1; } u32 ok = X[i], ng = 0; while (ok - ng > 1) { u32 md = (ok + ng) >> 1; (max.fold(md, X[i] + 1) < Y[i] ? ok : ng) = md; } return ok; }(); if (idx == X[i] + 1) { // std::cout << 0 << ' '; continue; } u32 cur = sum.fold(idx, X[i] + 1).first; sum.modify(idx, X[i] + 1, Y[i]); max.modify(idx, X[i] + 1, Y[i]); u32 next = sum.fold(idx, X[i] + 1).first; res[i] = next - cur; // std::cout << res[i] << ' '; } // std::cout << '\n'; return res; } int main() { size_t N; std::cin >> N; std::array, 4> X; X.fill(std::vector(N)); std::array, 4> Y; Y.fill(std::vector(N)); for (auto i: range(0, N)) { i32 x1, y1, x2, y2; std::cin >> x1 >> y1 >> x2 >> y2; X[0][i] = X[3][i] = x2; X[1][i] = X[2][i] = -x1; Y[0][i] = Y[1][i] = y2; Y[2][i] = Y[3][i] = -y1; } std::array, 4> ans; for (auto i: range(0, 4)) { ans[i] = solve(X[i], Y[i]); } for (auto i: range(0, N)) { u32 tmp = 0; for (auto j: range(0, 4)) { tmp += ans[j][i]; } std::cout << tmp << '\n'; } return 0; }