cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub NotLeonian/cp-library-cpp

:heavy_check_mark: test/src/datastructure/segment_tree/commutative_dual_segment_tree/rectilinear_polygons.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc211/tasks/abc211_f"

#include <algorithm>
#include <iostream>
#include <tuple>

#include "library/datastructure/segment_tree/commutative_dual_segment_tree.hpp"
using suisen::CommutativeDualSegmentTree;

constexpr int M = 100010;

int mapping(int f, int x) { return f + x; }
int composition(int f, int g) { return f + g; }
int id() { return 0; }

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<std::vector<std::tuple<int, int, int>>> event(M);
    CommutativeDualSegmentTree<int, int, mapping, composition, id> seg1(M, 0);
    for (int i = 0; i < n; ++i) {
        int m;
        std::cin >> m;
        std::vector<std::pair<int, int>> polygon(m);
        for (int j = 0; j < m; ++j) {
            int x, y;
            std::cin >> x >> y;
            polygon[j] = {x, y};
        }
        std::vector<std::tuple<int, int, int>> t;
        for (int j = 0; j < m; j += 2) {
            auto [x, y1] = polygon[j];
            auto [_, y2] = polygon[j + 1];
            t.emplace_back(x, std::min(y1, y2), std::max(y1, y2));
        }
        std::sort(t.begin(), t.end());
        for (auto [x, yl, yr] : t) {
            int sgn = seg1[yl] & 1 ? -1 : 1;
            event[x].emplace_back(yl, yr, sgn);
            seg1.apply(yl, yr, 1);
        }
        for (auto [_, yl, yr] : t) {
            seg1.apply(yl, yr, -1);
        }
    }
    int q;
    std::cin >> q;
    std::vector<std::tuple<int, int, int>> qs(q);
    for (int i = 0; i < q; ++i) {
        int x, y;
        std::cin >> x >> y;
        qs[i] = {x, y, i};
    }
    std::sort(qs.begin(), qs.end());
    std::vector<int> ans(q);
    CommutativeDualSegmentTree<int, int, mapping, composition, id> seg(M, 0);
    int prev = 0;
    for (auto [x, y, id] : qs) {
        for (; prev <= x; ++prev) {
            for (auto [yl, yr, sgn] : event[prev]) seg.apply(yl, yr, sgn);
        }
        ans[id] = seg[y];
    }
    for (auto v : ans) {
        std::cout << v << '\n';
    }
    return 0;
}
#line 1 "test/src/datastructure/segment_tree/commutative_dual_segment_tree/rectilinear_polygons.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc211/tasks/abc211_f"

#include <algorithm>
#include <iostream>
#include <tuple>

#line 1 "library/datastructure/segment_tree/commutative_dual_segment_tree.hpp"



#include <cassert>
#include <vector>

namespace suisen {
    template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
    struct CommutativeDualSegmentTree {
        CommutativeDualSegmentTree() = default;
        CommutativeDualSegmentTree(std::vector<T>&& a) : n(a.size()), m(ceil_pow2(a.size())), data(std::move(a)), lazy(m, id()) {}
        CommutativeDualSegmentTree(const std::vector<T>& a) : CommutativeDualSegmentTree(std::vector<T>(a)) {}
        CommutativeDualSegmentTree(int n, const T& fill_value) : CommutativeDualSegmentTree(std::vector<T>(n, fill_value)) {}

        T operator[](int i) const {
            assert(0 <= i and i < n);
            T res = data[i];
            for (i = (i + m) >> 1; i; i >>= 1) res = mapping(lazy[i], res);
            return res;
        }
        T get(int i) const {
            return (*this)[i];
        }
        void apply(int l, int r, const F& f) {
            assert(0 <= l and r <= n);
            for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
                if (l & 1) apply(l++, f);
                if (r & 1) apply(--r, f);
            }
        }
    protected:
        int n, m;
        std::vector<T> data;
        std::vector<F> lazy;

        void apply(int k, const F& f) {
            if (k < m) {
                lazy[k] = composition(f, lazy[k]);
            } else if (k - m < n) {
                data[k - m] = mapping(f, data[k - m]);
            }
        }
    private:
        static int ceil_pow2(int n) {
            int m = 1;
            while (m < n) m <<= 1;
            return m;
        }
    };
} // namespace suisen


#line 8 "test/src/datastructure/segment_tree/commutative_dual_segment_tree/rectilinear_polygons.test.cpp"
using suisen::CommutativeDualSegmentTree;

constexpr int M = 100010;

int mapping(int f, int x) { return f + x; }
int composition(int f, int g) { return f + g; }
int id() { return 0; }

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<std::vector<std::tuple<int, int, int>>> event(M);
    CommutativeDualSegmentTree<int, int, mapping, composition, id> seg1(M, 0);
    for (int i = 0; i < n; ++i) {
        int m;
        std::cin >> m;
        std::vector<std::pair<int, int>> polygon(m);
        for (int j = 0; j < m; ++j) {
            int x, y;
            std::cin >> x >> y;
            polygon[j] = {x, y};
        }
        std::vector<std::tuple<int, int, int>> t;
        for (int j = 0; j < m; j += 2) {
            auto [x, y1] = polygon[j];
            auto [_, y2] = polygon[j + 1];
            t.emplace_back(x, std::min(y1, y2), std::max(y1, y2));
        }
        std::sort(t.begin(), t.end());
        for (auto [x, yl, yr] : t) {
            int sgn = seg1[yl] & 1 ? -1 : 1;
            event[x].emplace_back(yl, yr, sgn);
            seg1.apply(yl, yr, 1);
        }
        for (auto [_, yl, yr] : t) {
            seg1.apply(yl, yr, -1);
        }
    }
    int q;
    std::cin >> q;
    std::vector<std::tuple<int, int, int>> qs(q);
    for (int i = 0; i < q; ++i) {
        int x, y;
        std::cin >> x >> y;
        qs[i] = {x, y, i};
    }
    std::sort(qs.begin(), qs.end());
    std::vector<int> ans(q);
    CommutativeDualSegmentTree<int, int, mapping, composition, id> seg(M, 0);
    int prev = 0;
    for (auto [x, y, id] : qs) {
        for (; prev <= x; ++prev) {
            for (auto [yl, yr, sgn] : event[prev]) seg.apply(yl, yr, sgn);
        }
        ans[id] = seg[y];
    }
    for (auto v : ans) {
        std::cout << v << '\n';
    }
    return 0;
}
Back to top page