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/graph/functional_graph/abc254_g.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc254/tasks/abc254_g"

#include <iostream>

#include "library/datastructure/util/range_set.hpp"
#include "library/graph/functional_graph.hpp"
#include "library/util/coordinate_compressor.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, q;
    std::cin >> n >> m >> q;

    std::vector<suisen::RangeSet<int, false>> range_sets(n);
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        std::cin >> a >> b >> c;
        --a, --b, --c;
        range_sets[a].insert(b, c);
    }

    suisen::CoordinateCompressorBuilder<int> comp_builder;
    std::vector<std::tuple<int, int, int, int>> queries(q);
    for (auto& [x, y, z, w] : queries) {
        std::cin >> x >> y >> z >> w;
        --x, --y, --z, --w;
        if (y > w) std::swap(x, z), std::swap(y, w);
        comp_builder.push(y);
    }

    std::vector<std::pair<int, int>> ranges;
    for (const auto& st : range_sets) for (const auto& [l, r] : st) {
        ranges.emplace_back(l, r);
        comp_builder.push(r);
    }
    std::sort(ranges.begin(), ranges.end());
    const int range_num = ranges.size();

    const auto comp = comp_builder.build();
    const int k = comp.size();

    suisen::FunctionalGraph g(k);
    {
        int i = 0, max_r = -1;
        for (int j = 0; j < k; ++j) {
            const int pos = comp.decomp(j);
            while (i < range_num and ranges[i].first <= pos) max_r = std::max(max_r, ranges[i++].second);
            g[j] = max_r < pos ? j : comp[max_r];
        }
    }
    const auto doubling = g.doubling(range_num);

    for (auto& [x, y, z, w] : queries) {
        const int ans = w - y;
        if (const auto itx = range_sets[x].find_range(y); itx != range_sets[x].end()) y = itx->second;
        if (const auto itz = range_sets[z].find_range(w); itz != range_sets[z].end()) w = itz->first;
        if (y >= w) {
            std::cout << ans + (x != z) << '\n';
        } else {
            const int w_ = w;
            const auto opt_res = doubling.step_until(comp[y], [&](int v) { return comp.decomp(v) >= w_; });
            std::cout << (opt_res.has_value() ? ans + opt_res->step + 1 : -1) << '\n';
        }
    }
    return 0;
}
#line 1 "test/src/graph/functional_graph/abc254_g.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc254/tasks/abc254_g"

#include <iostream>

#line 1 "library/datastructure/util/range_set.hpp"



#include <map>

namespace suisen {

template <typename T, bool merge_adjacent_segment = true>
struct RangeSet : public std::map<T, T> {
    public:
        RangeSet() : _size(0) {}

        // returns the number of integers in this set (not the number of ranges). O(1)
        T size() const { return number_of_elements(); }
        // returns the number of integers in this set (not the number of ranges). O(1)
        T number_of_elements() const { return _size; }
        // returns the number of ranges in this set (not the number of integers). O(1)
        int number_of_ranges() const { return std::map<T, T>::size(); }

        // returns whether the given integer is in this set or not. O(log N)
        bool contains(T x) const {
            auto it = this->upper_bound(x);
            return it != this->begin() and x <= std::prev(it)->second;
        }

        /**
         * returns the iterator pointing to the range [l, r] in this set s.t. l <= x <= r.
         * if such a range does not exist, returns `end()`.
         * O(log N)
         */
        auto find_range(T x) const {
            auto it = this->upper_bound(x);
            return it != this->begin() and x <= (--it)->second ? it : this->end();
        }

        // returns whether `x` and `y` is in this set and in the same range. O(log N)
        bool in_the_same_range(T x, T y) const {
            auto it = get_containing_range(x);
            return it != this->end() and it->first <= y and y <= it->second;
        }

        // inserts the range [x, x] and returns the number of integers inserted to this set. O(log N)
        T insert(T x) {
            return insert(x, x);
        }
        
        // inserts the range [l, r] and returns the number of integers inserted to this set. amortized O(log N)
        T insert(T l, T r) {
            if (l > r) return 0;
            auto it = this->upper_bound(l);
            if (it != this->begin() and is_mergeable(std::prev(it)->second, l)) {
                it = std::prev(it);
                l = std::min(l, it->first);
            }
            T inserted = 0;
            for (; it != this->end() and is_mergeable(r, it->first); it = std::map<T, T>::erase(it)) {
                auto [cl, cr] = *it; 
                r = std::max(r, cr);
                inserted -= cr - cl + 1;
            }
            inserted += r - l + 1;
            (*this)[l] = r;
            _size += inserted;
            return inserted;
        }

        // erases the range [x, x] and returns the number of integers erased from this set. O(log N)
        T erase(T x) {
            return erase(x, x);
        }

        // erases the range [l, r] and returns the number of integers erased from this set. amortized O(log N)
        T erase(T l, T r) {
            if (l > r) return 0;
            T tl = l, tr = r;
            auto it = this->upper_bound(l);
            if (it != this->begin() and l <= std::prev(it)->second) {
                it = std::prev(it);
                tl = it->first;
            }
            T erased = 0;
            for (; it != this->end() and it->first <= r; it = std::map<T, T>::erase(it)) {
                auto [cl, cr] = *it;
                tr = cr;
                erased += cr - cl + 1;
            }
            if (tl < l) {
                (*this)[tl] = l - 1;
                erased -= l - tl;
            }
            if (r < tr) {
                (*this)[r + 1] = tr;
                erased -= tr - r;
            }
            _size -= erased;
            return erased;
        }

        // returns minimum integer x s.t. x >= lower and x is NOT in this set
        T minimum_excluded(T lower = 0) const {
            static_assert(merge_adjacent_segment);
            auto it = find_range(lower);
            return it == this->end() ? lower : it->second + 1;
        }

        // returns maximum integer x s.t. x <= upper and x is NOT in this set
        T maximum_excluded(T upper) const {
            static_assert(merge_adjacent_segment);
            auto it = find_range(upper);
            return it == this->end() ? upper : it->first - 1;
        }

    private:
        T _size;

        bool is_mergeable(T cur_r, T next_l) {
            return next_l <= cur_r + merge_adjacent_segment;
        }
};

} // namespace suisen


#line 1 "library/graph/functional_graph.hpp"



#include <cassert>
#include <cstdint>
#include <optional>
#include <tuple>
#include <utility>
#include <vector>

namespace suisen {
    struct FunctionalGraph {
        struct Doubling;
        template <typename T, T(*)(T, T), T(*)()>
        struct DoublingSum;
        friend struct Doubling;
        template <typename T, T(*op)(T, T), T(*e)()>
        friend struct DoublingSum;

        FunctionalGraph() : FunctionalGraph(0) {}
        FunctionalGraph(int n) : _n(n), _nxt(n) {}
        FunctionalGraph(const std::vector<int>& nxt) : _n(nxt.size()), _nxt(nxt) {}

        const int& operator[](int u) const {
            return _nxt[u];
        }
        int& operator[](int u) {
            return _nxt[u];
        }

        struct Doubling {
            friend struct FunctionalGraph;

            int query(int u, long long d) const {
                for (int l = _log; l >= 0; --l) if ((d >> l) & 1) u = _nxt[l][u];
                return u;
            }

            struct BinarySearchResult {
                int v;
                long long step;
                operator std::pair<int, long long>() const { return std::pair<int, long long>{ v, step }; }
            };

            template <typename Pred>
            auto max_step(int u, Pred &&f) const {
                assert(f(u));
                long long step = 0;
                for (int l = _log; l >= 0; --l) if (int nxt_u = _nxt[l][u]; f(nxt_u)) {
                    u = nxt_u, step |= 1LL << l;
                }
                return BinarySearchResult{ u, step };
            }

            template <typename Pred>
            std::optional<BinarySearchResult> step_until(int u, Pred &&f) const {
                if (f(u)) return BinarySearchResult { u, 0 };
                auto [v, step] = max_step(u, [&](int v) { return not f(v); });
                v = _nxt[0][v], ++step;
                if (not f(v)) return std::nullopt;
                return BinarySearchResult{ v, step };
            }

        private:
            int _n, _log;
            std::vector<std::vector<int>> _nxt;

            Doubling(const std::vector<int>& nxt, long long max_step) : _n(nxt.size()), _log(floor_log2(max_step)), _nxt(_log + 1, std::vector<int>(_n)) {
                _nxt[0] = nxt;
                for (int i = 1; i <= _log; ++i) for (int j = 0; j < _n; ++j) {
                    _nxt[i][j] = _nxt[i - 1][_nxt[i - 1][j]];
                }
            }
        };

        template <typename T, T(*op)(T, T), T(*e)()>
        struct DoublingSum : private Doubling {
            friend struct FunctionalGraph;

            struct Result {
                int v;
                T sum;
                operator std::pair<int, T>() const { return std::pair<int, T>{ v, sum }; }
            };

            auto query(int u, long long d) const {
                T sum = e();
                for (int l = _log; l >= 0; --l) if ((d >> l) & 1) sum = op(sum, _dat[l][std::exchange(u, _nxt[l][u])]);
                return Result{ u, sum };
            }

            struct BinarySearchResult {
                int v;
                T sum;
                long long step;
                operator std::tuple<int, T, long long>() const { return std::tuple<int, T, long long>{ v, sum, step }; }
            };

            template <typename Pred>
            auto max_step(int u, Pred &&f) const {
                assert(f(e()));
                long long step = 0;
                T sum = e();
                for (int l = _log; l >= 0; --l) {
                    if (T nxt_sum = op(sum, _dat[l][u]); f(nxt_sum)) {
                        sum = std::move(nxt_sum), u = _nxt[l][u], step |= 1LL << l;
                    }
                }
                return BinarySearchResult{ u, sum, step };
            }
            template <typename Pred>
            std::optional<BinarySearchResult> step_until(int u, Pred &&f) const {
                if (f(e())) return BinarySearchResult { u, e(), 0 };
                auto [v, sum, step] = max_step(u, [&](const T& v) { return not f(v); });
                sum = op(sum, _dat[0][v]), v = _nxt[0][v], ++step;
                if (not f(sum)) return std::nullopt;
                return BinarySearchResult{ v, sum, step };
            }

        private:
            std::vector<std::vector<T>> _dat;

            DoublingSum(const std::vector<int>& nxt, long long max_step, const std::vector<T>& dat) : Doubling(nxt, max_step), _dat(_log + 1, std::vector<T>(_n, e())) {
                _dat[0] = dat;
                for (int i = 1; i <= _log; ++i) for (int j = 0; j < _n; ++j) {
                    _dat[i][j] = op(_dat[i - 1][j], _dat[i - 1][_nxt[i - 1][j]]);
                }
            }
        };

        Doubling doubling(long long max_step) const {
            return Doubling(_nxt, max_step);
        }

        template <typename T, T(*op)(T, T), T(*e)()>
        DoublingSum<T, op, e> doubling(long long max_step, const std::vector<T>& dat) const {
            return DoublingSum<T, op, e>(_nxt, max_step, dat);
        }

        struct InfinitePath {
            int head_v;
            int head_len;
            int loop_v;
            int loop_len;
            InfinitePath() = default;
            InfinitePath(int head_v, int head_len, int loop_v, int loop_len) : head_v(head_v), head_len(head_len), loop_v(loop_v), loop_len(loop_len) {}
        };

        std::vector<InfinitePath> infinite_paths() const {
            std::vector<InfinitePath> res(_n);

            std::vector<int> vis(_n, _n);
            std::vector<int> dep(_n, 0);

            int time = 0;
            auto dfs = [&](auto dfs, int u) -> int {
                vis[u] = time;
                int v = _nxt[u];
                if (vis[v] == vis[u]) { // found cycle
                    int loop_len = dep[u] - dep[v] + 1;
                    res[u] = { u, 0, u, loop_len };
                    return loop_len - 1;
                } else if (vis[v] < vis[u]) {
                    res[u] = { u, res[v].head_len + 1, res[v].loop_v, res[v].loop_len };
                    return 0;
                } else {
                    dep[v] = dep[u] + 1;
                    int c = dfs(dfs, v);
                    if (c > 0) { // in cycle
                        res[u] = { u, 0, u, res[v].loop_len };
                        return c - 1;
                    } else { // out of cycle
                        res[u] = { u, res[v].head_len + 1, res[v].loop_v, res[v].loop_len };
                        return 0;
                    }
                }
            };
            for (int i = 0; i < _n; ++i, ++time) if (vis[i] == _n) dfs(dfs, i);
            return res;
        }

        /**
         * Calculates k'th iterate: f(f(f(...f(i)))) for all 0 <= i < N in O(N) time.
         * Reference: https://noshi91.hatenablog.com/entry/2019/09/22/114149
         */
        std::vector<int> kth_iterate(const long long k) const {
            assert(k >= 0);
            std::vector<int> res(_n);
            std::vector<int> forest_roots;
            std::vector<std::vector<int>> forest(_n);
            std::vector<std::vector<std::pair<long long, int>>> qs(_n);
            for (const auto& path : infinite_paths()) {
                const int v = path.head_v;
                (path.head_len == 0 ? forest_roots : forest[_nxt[v]]).push_back(v);
                if (path.head_len >= k) continue;
                qs[path.loop_v].emplace_back(k - path.head_len, v);
            }
            std::vector<int> dfs_path(_n);
            auto dfs = [&](auto dfs, int u, int d) -> void {
                dfs_path[d] = u;
                if (d >= k) res[u] = dfs_path[d - k];
                for (int v : forest[u]) dfs(dfs, v, d + 1);
            };
            for (int root : forest_roots) dfs(dfs, root, 0);
            std::vector<int8_t> seen(_n, false);
            for (int root : forest_roots) {
                if (seen[root]) continue;
                std::vector<int> cycle{ root };
                for (int v = _nxt[root]; v != root; v = _nxt[v]) cycle.push_back(v);
                const int len = cycle.size();
                for (int i = 0; i < len; ++i) {
                    const int s = cycle[i];
                    seen[s] = true;
                    for (const auto& [rem, res_index] : qs[s]) {
                        res[res_index] = cycle[(i + rem) % len];
                    }
                }
            }
            return res;
        }

    private:
        int _n;
        std::vector<int> _nxt;

        static int floor_log2(long long v) {
            int l = 0;
            while (1LL << (l + 1) <= v) ++l;
            return l;
        }
    };
} // namespace suisen



#line 1 "library/util/coordinate_compressor.hpp"



#include <algorithm>
#line 7 "library/util/coordinate_compressor.hpp"

#line 1 "library/type_traits/type_traits.hpp"



#include <limits>
#line 6 "library/type_traits/type_traits.hpp"
#include <type_traits>

namespace suisen {
    template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>;

    template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; };
    template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; };
    template <typename T> static constexpr int bitnum_v = bitnum<T>::value;
    template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; };
    template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value;

    template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; };
    template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type;

    template <typename T, typename = void> struct rec_value_type { using type = T; };
    template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> {
        using type = typename rec_value_type<typename T::value_type>::type;
    };
    template <typename T> using rec_value_type_t = typename rec_value_type<T>::type;

    template <typename T> class is_iterable {
        template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value;
    template <typename T> class is_writable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_writable_v = is_writable<T>::value;
    template <typename T> class is_readable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_readable_v = is_readable<T>::value;
} // namespace suisen

#line 9 "library/util/coordinate_compressor.hpp"

namespace suisen {
template <typename T>
class CoordinateCompressorBuilder {
    public:
        struct Compressor {
            public:
                static constexpr int absent = -1;

                // default constructor
                Compressor() : _xs(std::vector<T>{}) {}
                // Construct from strictly sorted vector
                Compressor(const std::vector<T> &xs) : _xs(xs) {
                    assert(is_strictly_sorted(xs));
                }

                // Return the number of distinct keys.
                int size() const {
                    return _xs.size();
                }
                // Check if the element is registered.
                bool has_key(const T &e) const {
                    return std::binary_search(_xs.begin(), _xs.end(), e);
                }
                // Compress the element. if not registered, returns `default_value`. (default: Compressor::absent)
                int comp(const T &e, int default_value = absent) const {
                    const int res = min_geq_index(e);
                    return res != size() and _xs[res] == e ? res : default_value;
                }
                // Restore the element from the index.
                T decomp(const int compressed_index) const {
                    return _xs[compressed_index];
                }
                // Compress the element. Equivalent to call `comp(e)`
                int operator[](const T &e) const {
                    return comp(e);
                }
                // Return the minimum registered value greater than `e`. if not exists, return `default_value`.
                T min_gt(const T &e, const T &default_value) const {
                    auto it = std::upper_bound(_xs.begin(), _xs.end(), e);
                    return it == _xs.end() ? default_value : *it;
                }
                // Return the minimum registered value greater than or equal to `e`. if not exists, return `default_value`.
                T min_geq(const T &e, const T &default_value) const {
                    auto it = std::lower_bound(_xs.begin(), _xs.end(), e);
                    return it == _xs.end() ? default_value : *it;
                }
                // Return the maximum registered value less than `e`. if not exists, return `default_value`
                T max_lt(const T &e, const T &default_value) const {
                    auto it = std::upper_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>());
                    return it == _xs.rend() ? default_value : *it;
                }
                // Return the maximum registered value less than or equal to `e`. if not exists, return `default_value`
                T max_leq(const T &e, const T &default_value) const {
                    auto it = std::lower_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>());
                    return it == _xs.rend() ? default_value : *it;
                }
                // Return the compressed index of the minimum registered value greater than `e`. if not exists, return `compressor.size()`.
                int min_gt_index(const T &e) const {
                    return std::upper_bound(_xs.begin(), _xs.end(), e) - _xs.begin();
                }
                // Return the compressed index of the minimum registered value greater than or equal to `e`. if not exists, return `compressor.size()`.
                int min_geq_index(const T &e) const {
                    return std::lower_bound(_xs.begin(), _xs.end(), e) - _xs.begin();
                }
                // Return the compressed index of the maximum registered value less than `e`. if not exists, return -1.
                int max_lt_index(const T &e) const {
                    return int(_xs.rend() - std::upper_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>())) - 1;
                }
                // Return the compressed index of the maximum registered value less than or equal to `e`. if not exists, return -1.
                int max_leq_index(const T &e) const {
                    return int(_xs.rend() - std::lower_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>())) - 1;
                }
            private:
                std::vector<T> _xs;
                static bool is_strictly_sorted(const std::vector<T> &v) {
                    return std::adjacent_find(v.begin(), v.end(), std::greater_equal<T>()) == v.end();
                }
        };
        CoordinateCompressorBuilder() : _xs(std::vector<T>{}) {}
        explicit CoordinateCompressorBuilder(const std::vector<T> &xs) : _xs(xs) {}
        explicit CoordinateCompressorBuilder(std::vector<T> &&xs) : _xs(std::move(xs)) {}
        template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr>
        CoordinateCompressorBuilder(const int n, Gen generator) {
            reserve(n);
            for (int i = 0; i < n; ++i) push(generator(i));
        }
        // Attempt to preallocate enough memory for specified number of elements.
        void reserve(int n) {
            _xs.reserve(n);
        }
        // Add data.
        void push(const T &first) {
            _xs.push_back(first);
        }
        // Add data.
        void push(T &&first) {
            _xs.push_back(std::move(first));
        }
        // Add data in the range of [first, last). 
        template <typename Iterator>
        auto push(const Iterator &first, const Iterator &last) -> decltype(std::vector<T>{}.push_back(*first), void()) {
            for (auto it = first; it != last; ++it) _xs.push_back(*it);
        }
        // Add all data in the container. Equivalent to `push(iterable.begin(), iterable.end())`.
        template <typename Iterable>
        auto push(const Iterable &iterable) -> decltype(std::vector<T>{}.push_back(*iterable.begin()), void()) {
            push(iterable.begin(), iterable.end());
        }
        // Add data.
        template <typename ...Args>
        void emplace(Args &&...args) {
            _xs.emplace_back(std::forward<Args>(args)...);
        }
        // Build compressor.
        auto build() {
            std::sort(_xs.begin(), _xs.end()), _xs.erase(std::unique(_xs.begin(), _xs.end()), _xs.end());
            return Compressor {_xs};
        }
        // Build compressor from vector.
        static auto build(const std::vector<T> &xs) {
            return CoordinateCompressorBuilder(xs).build();
        }
        // Build compressor from vector.
        static auto build(std::vector<T> &&xs) {
            return CoordinateCompressorBuilder(std::move(xs)).build();
        }
        // Build compressor from generator.
        template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr>
        static auto build(const int n, Gen generator) {
            return CoordinateCompressorBuilder<T>(n, generator).build();
        }
    private:
        std::vector<T> _xs;
};

} // namespace suisen


#line 8 "test/src/graph/functional_graph/abc254_g.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, q;
    std::cin >> n >> m >> q;

    std::vector<suisen::RangeSet<int, false>> range_sets(n);
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        std::cin >> a >> b >> c;
        --a, --b, --c;
        range_sets[a].insert(b, c);
    }

    suisen::CoordinateCompressorBuilder<int> comp_builder;
    std::vector<std::tuple<int, int, int, int>> queries(q);
    for (auto& [x, y, z, w] : queries) {
        std::cin >> x >> y >> z >> w;
        --x, --y, --z, --w;
        if (y > w) std::swap(x, z), std::swap(y, w);
        comp_builder.push(y);
    }

    std::vector<std::pair<int, int>> ranges;
    for (const auto& st : range_sets) for (const auto& [l, r] : st) {
        ranges.emplace_back(l, r);
        comp_builder.push(r);
    }
    std::sort(ranges.begin(), ranges.end());
    const int range_num = ranges.size();

    const auto comp = comp_builder.build();
    const int k = comp.size();

    suisen::FunctionalGraph g(k);
    {
        int i = 0, max_r = -1;
        for (int j = 0; j < k; ++j) {
            const int pos = comp.decomp(j);
            while (i < range_num and ranges[i].first <= pos) max_r = std::max(max_r, ranges[i++].second);
            g[j] = max_r < pos ? j : comp[max_r];
        }
    }
    const auto doubling = g.doubling(range_num);

    for (auto& [x, y, z, w] : queries) {
        const int ans = w - y;
        if (const auto itx = range_sets[x].find_range(y); itx != range_sets[x].end()) y = itx->second;
        if (const auto itz = range_sets[z].find_range(w); itz != range_sets[z].end()) w = itz->first;
        if (y >= w) {
            std::cout << ans + (x != z) << '\n';
        } else {
            const int w_ = w;
            const auto opt_res = doubling.step_until(comp[y], [&](int v) { return comp.decomp(v) >= w_; });
            std::cout << (opt_res.has_value() ? ans + opt_res->step + 1 : -1) << '\n';
        }
    }
    return 0;
}
Back to top page