cp-library-cpp

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

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

:heavy_check_mark: test/src/datastructure/lazy_eval_map/leq_and_neq.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/arc115/tasks/arc115_e"

#include <algorithm>
#include <iostream>
#include <atcoder/modint>

using mint = atcoder::modint998244353;

#include "library/util/coordinate_compressor.hpp"
#include "library/datastructure/lazy_eval_map.hpp"

using suisen::CoordinateCompressorBuilder;
using suisen::LazyEvalMap;

struct S {
    mint sum;
    int len;
};
struct F {
    mint a, b;
};

S op(S x, S y) {
    return { x.sum + y.sum, x.len + y.len };
}
S e() {
    return { 0, 0 };
}
S mapping(F f, S x) {
    return { x.sum * f.a + x.len * f.b, x.len };
}
F composition(F f, F g) {
    return { f.a * g.a, f.a * g.b + f.b };
}
F id() {
    return { 1, 0 };
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int &e : a) std::cin >> e;
    CoordinateCompressorBuilder<int> builder(a);
    builder.push(0);
    auto comp = builder.build();
    int m = comp.size();
    LazyEvalMap<int, S, op, e, F, mapping, composition, id> mp;
    for (int i = 1; i < m; ++i) {
        int len = comp.decomp(i) - comp.decomp(i - 1);
        mp[i - 1] = { 0, len };
    }
    mint sum = 1;
    for (int v : a) {
        mp.apply_all({ -1, sum });
        mp.apply_by_key(comp[v], m, { 0, 0 });
        sum = mp.prod_all().sum;
    }
    std::cout << mp.prod_all().sum.val() << '\n';
    return 0;
}
#line 1 "test/src/datastructure/lazy_eval_map/leq_and_neq.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/arc115/tasks/arc115_e"

#include <algorithm>
#include <iostream>
#include <atcoder/modint>

using mint = atcoder::modint998244353;

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



#line 5 "library/util/coordinate_compressor.hpp"
#include <cassert>
#include <vector>

#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 1 "library/datastructure/lazy_eval_map.hpp"



#line 5 "library/datastructure/lazy_eval_map.hpp"
#include <tuple>

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



#line 5 "library/util/update_proxy_object.hpp"

namespace suisen {

template <typename T, typename UpdateFunc, constraints_t<std::is_invocable<UpdateFunc>> = nullptr>
struct UpdateProxyObject {
    public:
        UpdateProxyObject(T &v, UpdateFunc update) : v(v), update(update) {}
        operator T() const { return v; }
        auto& operator++() && { ++v, update(); return *this; }
        auto& operator--() && { --v, update(); return *this; }
        auto& operator+=(const T &val) && { v += val, update(); return *this; }
        auto& operator-=(const T &val) && { v -= val, update(); return *this; }
        auto& operator*=(const T &val) && { v *= val, update(); return *this; }
        auto& operator/=(const T &val) && { v /= val, update(); return *this; }
        auto& operator%=(const T &val) && { v %= val, update(); return *this; }
        auto& operator =(const T &val) && { v  = val, update(); return *this; }
        auto& operator<<=(const T &val) && { v <<= val, update(); return *this; }
        auto& operator>>=(const T &val) && { v >>= val, update(); return *this; }
        template <typename F, constraints_t<std::is_invocable_r<T, F, T>> = nullptr>
        auto& apply(F f) && { v = f(v), update(); return *this; }
    private:
        T &v;
        UpdateFunc update;
};

} // namespace suisen


#line 1 "library/datastructure/range_foldable_map.hpp"



#line 6 "library/datastructure/range_foldable_map.hpp"

#line 1 "library/datastructure/splay_tree_map.hpp"



#line 5 "library/datastructure/splay_tree_map.hpp"
#include <cstddef>
#line 7 "library/datastructure/splay_tree_map.hpp"
#include <utility>

namespace suisen {
namespace internal::splay_tree_map {

template <typename Key, typename Val, typename Derived>
struct MapNodeBase {
    using node_ptr_t = Derived *;

    Key key;
    Val val;
    int siz;
    node_ptr_t ch[2] {nullptr, nullptr};

    MapNodeBase() : key(), val(), siz(1) {}
    MapNodeBase(const Key &key, const Val &val) : key(key), val(val), siz(1) {}

    ~MapNodeBase() {
        delete ch[0];
        delete ch[1];
    }

    void update() {
        siz = 1 + size(ch[0]) + size(ch[1]);
    }
    void push() {}

    static int size(node_ptr_t node) {
        return node == nullptr ? 0 : node->siz;
    }

    static node_ptr_t rotate(node_ptr_t node, bool is_right) {
        node_ptr_t root = node->ch[is_right ^ true];
        node->ch[is_right ^ true] = root->ch[is_right];
        root->ch[is_right] = node;
        node->update(), root->update();
        return root;
    }

    static node_ptr_t splay_by_index(node_ptr_t node, int index) {
        std::vector<node_ptr_t> path;
        node_ptr_t work_root = new Derived();
        node_ptr_t work_leaf[2] { work_root, work_root };
        while (true) {
            node->push();
            int size_l = size(node->ch[0]);
            bool is_right = index > size_l;
            node_ptr_t next_node = node->ch[is_right];
            if (index == size_l or next_node == nullptr) { // found the target node
                break;
            }
            if (is_right) {
                index -= size_l + 1;
            }
            int size_l_ch = size(next_node->ch[0]);
            if (index != size_l_ch) {
                bool is_right_ch = index > size_l_ch;
                if (is_right_ch == is_right) { // zig-zig
                    if (is_right_ch) {
                        index -= size_l_ch + 1;
                    }
                    next_node->push();
                    node = rotate(node, is_right ^ true);
                    next_node = node->ch[is_right];
                    if (next_node == nullptr) { // found the target node
                        break;
                    }
                }
            }
            path.push_back(node);
            work_leaf[is_right]->ch[is_right] = node;
            work_leaf[is_right] = node;
            node = next_node;
        }
        work_leaf[0]->ch[0] = node->ch[1];
        work_leaf[1]->ch[1] = node->ch[0];
        node->ch[0] = work_root->ch[1];
        node->ch[1] = work_root->ch[0];
    
        work_root->ch[0] = work_root->ch[1] = nullptr;
        delete work_root;

        while (path.size()) {
            path.back()->update(), path.pop_back();
        }
        node->update();

        return node;
    }

    static node_ptr_t splay_by_key(node_ptr_t node, const Key &x) {
        if (node == nullptr) return node;
        std::vector<node_ptr_t> path;
        node_ptr_t work_root = new Derived();
        node_ptr_t work_leaf[2] { work_root, work_root };
        while (true) {
            node->push();
            if (x == node->key) {
                break;
            }
            bool is_right = x > node->key;
            node_ptr_t next_node = node->ch[is_right];
            if (next_node == nullptr) {
                break;
            }
            if (x != next_node->key) {
                bool is_right_ch = x > next_node->key;
                if (is_right_ch == is_right) { // zig-zig
                    next_node->push();
                    node = rotate(node, is_right ^ true);
                    next_node = node->ch[is_right];
                    if (next_node == nullptr) { // found the target node
                        break;
                    }
                }
            }
            path.push_back(node);
            work_leaf[is_right]->ch[is_right] = node;
            work_leaf[is_right] = node;
            node = next_node;
        }
        work_leaf[0]->ch[0] = node->ch[1];
        work_leaf[1]->ch[1] = node->ch[0];
        node->ch[0] = work_root->ch[1];
        node->ch[1] = work_root->ch[0];

        work_root->ch[0] = work_root->ch[1] = nullptr;
        delete work_root;

        while (path.size()) {
            path.back()->update(), path.pop_back();
        }
        node->update();

        return node;
    }
    static std::pair<node_ptr_t, bool> find_key(node_ptr_t node, const Key &key) {
        if (node == nullptr) return { node, false };
        node = splay_by_key(node, key);
        return { node, node->key == key };
    }
    static std::pair<node_ptr_t, node_ptr_t> split_by_index(node_ptr_t node, int k) {
        if (k == 0) return { nullptr, node };
        if (k == size(node)) return { node, nullptr };
        node_ptr_t r = splay_by_index(node, k);
        node_ptr_t l = r->ch[0];
        r->ch[0] = nullptr;
        r->update();
        return { l, r };
    }
    static std::tuple<node_ptr_t, node_ptr_t, node_ptr_t> split_by_index(node_ptr_t node, int l, int r) {
        auto [tl, tmr] = split_by_index(node, l);
        auto [tm, tr] = split_by_index(tmr, r - l);
        return { tl, tm, tr };
    }
    static std::pair<node_ptr_t, node_ptr_t> split_by_key(node_ptr_t node, const Key &key) {
        if (node == nullptr) return { nullptr, nullptr };
        node_ptr_t r = splay_by_key(node, key);
        if (r->key >= key) {
            node_ptr_t l = r->ch[0];
            r->ch[0] = nullptr;
            r->update();
            return { l, r };
        } else {
            node_ptr_t l = r->ch[1];
            r->ch[1] = nullptr;
            r->update();
            return { r, l };
        }
    }
    static std::tuple<node_ptr_t, node_ptr_t, node_ptr_t> split_by_key(node_ptr_t node, const Key &l, const Key &r) {
        auto [tl, tmr] = split_by_key(node, l);
        auto [tm, tr] = split_by_key(tmr, r);
        return { tl, tm, tr };
    }
    static node_ptr_t merge(node_ptr_t l, node_ptr_t r) {
        if (l == nullptr) return r;
        if (r == nullptr) return l;
        node_ptr_t new_root = splay_by_index(r, 0);
        new_root->ch[0] = l;
        new_root->update();
        return new_root;
    }
    static node_ptr_t merge(node_ptr_t tl, node_ptr_t tm, node_ptr_t tr) {
        return merge(merge(tl, tm), tr);
    }
    static node_ptr_t insert(node_ptr_t node, const Key &key, const Val &val, bool overwrite = true) {
        auto [l, r] = split_by_key(node, key);
        if (r != nullptr and r->key == key) {
            if (overwrite) {
                r->val = val;
                r->update();
            }
            return merge(l, r);
        }
        node_ptr_t new_node = new Derived(key, val);
        new_node->ch[0] = l;
        new_node->ch[1] = r;
        new_node->update();
        return new_node;
    }
    static node_ptr_t erase_index(node_ptr_t node, int index) {
        auto [l, r] = split(index ? node : splay(node, 0), index);
        assert(r->ch[0] == nullptr);
        node_ptr_t res = merge(l, r->ch[1]);
        r->ch[1] = nullptr;
        delete r;
        return res;
    }
    static std::pair<node_ptr_t, bool> erase_key(node_ptr_t node, const Key &key) {
        auto [l, r] = split_by_key(node, key);
        if (r == nullptr or r->key != key) return { merge(l, r), false };
        assert(r->ch[0] == nullptr);
        node_ptr_t res = merge(l, r->ch[1]);
        r->ch[1] = nullptr;
        delete r;
        return { res, true };
    }
    static Val get_or_default(node_ptr_t node, const Key &key, const Val &default_value) {
        auto [new_root, found] = find_key(node, key);
        node = new_root;
        return found ? new_root->val : default_value;
    }
};

template <typename Key, typename Val>
struct SplayTreeMapNode : public MapNodeBase<Key, Val, SplayTreeMapNode<Key, Val>> {
    using Base = MapNodeBase<Key, Val, SplayTreeMapNode<Key, Val>>;
    using Base::MapNodeBase;
    using node_ptr_t = typename Base::node_ptr_t;
};
}

template <typename Key, typename Val>
class SplayTreeMap {
    protected:
        using Node = internal::splay_tree_map::SplayTreeMapNode<Key, Val>;
        using node_ptr_t = typename Node::node_ptr_t;
    public:
        SplayTreeMap() : root(nullptr) {}
        ~SplayTreeMap() {
            delete root;
        }

        SplayTreeMap& operator=(const SplayTreeMap&) = delete;
        SplayTreeMap& operator=(SplayTreeMap&& other) {
            if (other.root == root) return *this;
            delete root;
            root = other.root;
            other.root = nullptr;
            return *this;
        }

        int size() {
            return Node::size(root);
        }
        bool contains(const Key &key) {
            auto [new_root, found] = Node::find_key(root, key);
            root = new_root;
            return found;
        }
        void insert(const Key &key, const Val &val) {
            root = Node::insert(root, key, val, true);
        }
        void insert_if_absent(const Key &key, const Val &val) {
            root = Node::insert(root, key, val, false);
        }
        bool erase_key(const Key &key) {
            auto [new_root, is_erased] = Node::erase_key(root, key);
            root = new_root;
            return is_erased;
        }
        void erase_index(int k) {
            index_bounds_check(k, size() + 1);
            root = Node::erase_index(root, k);
        }
        Val& get_or_create(const Key &key, const Val &val) {
            root = Node::insert(root, key, val, false);
            return root->val;
        }
        Val& operator[](const Key &key) {
            return get_or_create(key, Val{});
        }
        Val get_or_default(const Key &key, const Val &default_value) {
            auto [new_root, res] = Node::get_or_default(root, key, default_value);
            root = new_root;
            return res;
        }
        std::pair<Key, Val> kth_entry(int k) {
            index_bounds_check(k, size());
            root = Node::splay_by_index(root, k);
            return { root->key, root->val };
        }
        SplayTreeMap split_by_index(int k) {
            index_bounds_check(k, size() + 1);
            auto [l, r] = Node::split_by_index(root, k);
            root = l;
            return SplayTreeMap<Key, Val>(r);
        }
        SplayTreeMap split_by_key(const Key &key) {
            auto [l, r] = Node::split_by_key(root, key);
            root = l;
            return SplayTreeMap<Key, Val>(r);
        }
        void merge(SplayTreeMap &&r) {
            assert(root != r.root);
            root = Node::merge(root, r.root);
            r.root = nullptr;
        }
        void swap(SplayTreeMap &r) {
            std::swap(root, r.root);
        }

    protected:
        Node *root;

        SplayTreeMap(node_ptr_t root) : root(root) {}
    
        static void index_bounds_check(unsigned int k, unsigned int n) {
            assert(k < n);
        }
        static void range_bounds_check(unsigned int l, unsigned int r, unsigned int n) {
            assert(l <= r and r <= n);
        }
};

}


#line 9 "library/datastructure/range_foldable_map.hpp"

namespace suisen {
namespace internal::range_foldable_map {

template <typename Key, typename Val, Val(*op)(Val, Val), Val (*e)(), typename Derived>
struct RangeFoldableMapNodeBase : public internal::splay_tree_map::MapNodeBase<Key, Val, Derived> {
    using Base = internal::splay_tree_map::MapNodeBase<Key, Val, Derived>;
    using node_ptr_t = typename Base::node_ptr_t;
    Val dat;
    RangeFoldableMapNodeBase() : RangeFoldableMapNodeBase(Key{}, e()) {}
    RangeFoldableMapNodeBase(const Key &key, const Val &val) : Base::MapNodeBase(key, val), dat(val) {}
    void update() {
        Base::update();
        dat = op(op(prod_all(this->ch[0]), this->val), prod_all(this->ch[1]));
    }
    static Val prod_all(node_ptr_t node) {
        return node == nullptr ? e() : node->dat;
    }
    static std::pair<node_ptr_t, Val> prod_by_index(node_ptr_t node, int l, int r) {
        auto [tl, tm, tr] = Base::split_by_index(node, l, r);
        Val res = prod_all(tm);
        return { Base::merge(tl, tm, tr), res };
    }
    static std::pair<node_ptr_t, Val> prod_by_key(node_ptr_t node, const Key &l, const Key &r) {
        auto [tl, tm, tr] = Base::split_by_key(node, l, r);
        Val res = prod_all(tm);
        return { Base::merge(tl, tm, tr), res };
    }
};

template <typename Key, typename Val, Val(*op)(Val, Val), Val (*e)()>
struct RangeFoldableMapNode : public RangeFoldableMapNodeBase<Key, Val, op, e, RangeFoldableMapNode<Key, Val, op, e>> {
    using Base = RangeFoldableMapNodeBase<Key, Val, op, e, RangeFoldableMapNode<Key, Val, op, e>>;
    using Base::RangeFoldableMapNodeBase;
    using node_ptr_t = typename Base::node_ptr_t;
};
}

template <typename Key, typename Val, Val(*op)(Val, Val), Val (*e)()>
class RangeFoldableMap {
    using Node = internal::range_foldable_map::RangeFoldableMapNode<Key, Val, op, e>;
    using node_ptr_t = typename Node::node_ptr_t;
    public:
        RangeFoldableMap() : root(nullptr) {}
        ~RangeFoldableMap() {
            delete root;
        }

        RangeFoldableMap& operator=(const RangeFoldableMap&) = delete;
        RangeFoldableMap& operator=(RangeFoldableMap&& other) {
            if (other.root == root) return *this;
            delete root;
            root = other.root;
            other.root = nullptr;
            return *this;
        }

        int size() {
            return Node::size(root);
        }
        bool contains(const Key &key) {
            auto [new_root, found] = Node::find_key(root, key);
            root = new_root;
            return found;
        }
        void insert(const Key &key, const Val &val) {
            root = Node::insert(root, key, val, true);
        }
        void insert_if_absent(const Key &key, const Val &val) {
            root = Node::insert(root, key, val, false);
        }
        bool erase_key(const Key &key) {
            auto [new_root, is_erased] = Node::erase_key(root, key);
            root = new_root;
            return is_erased;
        }
        void erase_index(int k) {
            index_bounds_check(k, size() + 1);
            root = Node::erase_index(root, k);
        }
        Val& get_or_create(const Key &key, const Val &val) {
            root = Node::insert(root, key, val, false);
            return root->val;
        }

        auto operator[](const Key &key) {
            get_or_create(key, e());
            return UpdateProxyObject { root->val, [this]{ root->update(); } };
        }
        Val operator()(const Key &l, const Key &r) {
            return prod(l, r);
        }
        Val prod_by_key(const Key &l, const Key &r) {
            auto [new_root, res] = Node::prod_by_key(root, l, r);
            root = new_root;
            return res;
        }
        Val prod_by_index(int l, int r) {
            auto [new_root, res] = Node::prod_by_index(root, l, r);
            root = new_root;
            return res;
        }
        Val prod_all() {
            return Node::prod_all(root);
        }

        Val get_or_default(const Key &key, const Val &default_value) {
            auto [new_root, res] = Node::get_or_default(root, key, default_value);
            root = new_root;
            return res;
        }
        std::pair<Key, Val> kth_entry(int k) {
            index_bounds_check(k, size());
            root = Node::splay_by_index(root, k);
            return { root->key, root->val };
        }
        RangeFoldableMap split_by_index(int k) {
            index_bounds_check(k, size() + 1);
            auto [l, r] = Node::split_by_index(root, k);
            root = l;
            return RangeFoldableMap(r);
        }
        RangeFoldableMap split_by_key(const Key &key) {
            auto [l, r] = Node::split_by_key(root, key);
            root = l;
            return RangeFoldableMap(r);
        }
        void merge(RangeFoldableMap &&r) {
            assert(root == nullptr or root != r.root);
            root = Node::merge(root, r.root);
            r.root = nullptr;
        }
        void swap(RangeFoldableMap &r) {
            std::swap(root, r.root);
        }

    protected:
        Node *root;

        RangeFoldableMap(node_ptr_t root) : root(root) {}
    
        static void index_bounds_check(unsigned int k, unsigned int n) {
            assert(k < n);
        }
        static void range_bounds_check(unsigned int l, unsigned int r, unsigned int n) {
            assert(l <= r and r <= n);
        }
};

}


#line 9 "library/datastructure/lazy_eval_map.hpp"

namespace suisen {
namespace internal::lazy_eval_map {

template <typename Key, typename Val, Val(*op)(Val, Val), Val (*e)(), typename F, Val(*mapping)(F, Val), F(*composition)(F, F), F(*id)(), typename Derived>
struct LazyEvalMapNodeBase : public internal::range_foldable_map::RangeFoldableMapNodeBase<Key, Val, op, e, Derived> {
    using Base = internal::range_foldable_map::RangeFoldableMapNodeBase<Key, Val, op, e, Derived>;
    using node_ptr_t = typename Base::node_ptr_t;
    F laz;

    LazyEvalMapNodeBase() : LazyEvalMapNodeBase(Key{}, e()) {}
    LazyEvalMapNodeBase(const Key &key, const Val &val) : Base::RangeFoldableMapNodeBase(key, val), laz(id()) {}

    void push() {
        Base::push();
        apply_all(this->ch[0], laz), apply_all(this->ch[1], laz);
        laz = id();
    }
    static void apply_all(node_ptr_t node, const F &f) {
        if (node == nullptr) return;
        node->val = mapping(f, node->val);
        node->dat = mapping(f, node->dat);
        node->laz = composition(f, node->laz);
    }
    static node_ptr_t apply_by_key(node_ptr_t node, const Key &l, const Key &r, const F &f) {
        auto [tl, tm, tr] = Base::split_by_key(node, l, r);
        apply_all(tm, f);
        return Base::merge(tl, tm, tr);
    }
    static node_ptr_t apply_by_index(node_ptr_t node, int l, int r, const F &f) {
        auto [tl, tm, tr] = Base::split_by_index(node, l, r);
        apply_all(tm, f);
        return Base::merge(tl, tm, tr);
    }
};

template <typename Key, typename Val, Val(*op)(Val, Val), Val (*e)(), typename F, Val(*mapping)(F, Val), F(*composition)(F, F), F(*id)()>
struct LazyEvalMapNode : public LazyEvalMapNodeBase<Key, Val, op, e, F, mapping, composition, id, LazyEvalMapNode<Key, Val, op, e, F, mapping, composition, id>> {
    using Base = LazyEvalMapNodeBase<Key, Val, op, e, F, mapping, composition, id, LazyEvalMapNode<Key, Val, op, e, F, mapping, composition, id>>;
    using Base::LazyEvalMapNodeBase;
    using node_ptr_t = typename Base::node_ptr_t;
};
}

template <typename Key, typename Val, Val(*op)(Val, Val), Val (*e)(), typename F, Val(*mapping)(F, Val), F(*composition)(F, F), F(*id)()>
class LazyEvalMap {
    using Node = internal::lazy_eval_map::LazyEvalMapNode<Key, Val, op, e, F, mapping, composition, id>;
    using node_ptr_t = typename Node::node_ptr_t;
    public:
        LazyEvalMap() : root(nullptr) {}
        ~LazyEvalMap() {
            delete root;
        }

        LazyEvalMap& operator=(const LazyEvalMap&) = delete;
        LazyEvalMap& operator=(LazyEvalMap&& other) {
            if (other.root == root) return *this;
            delete root;
            root = other.root;
            other.root = nullptr;
            return *this;
        }

        int size() {
            return Node::size(root);
        }
        bool contains(const Key &key) {
            auto [new_root, found] = Node::find_key(root, key);
            root = new_root;
            return found;
        }
        void insert(const Key &key, const Val &val) {
            root = Node::insert(root, key, val, true);
        }
        void insert_if_absent(const Key &key, const Val &val) {
            root = Node::insert(root, key, val, false);
        }
        bool erase_key(const Key &key) {
            auto [new_root, is_erased] = Node::erase_key(root, key);
            root = new_root;
            return is_erased;
        }
        void erase_index(int k) {
            index_bounds_check(k, size() + 1);
            root = Node::erase_index(root, k);
        }
        Val& get_or_create(const Key &key, const Val &val) {
            root = Node::insert(root, key, val, false);
            return root->val;
        }

        auto operator[](const Key &key) {
            get_or_create(key, e());
            return UpdateProxyObject { root->val, [this]{ root->update(); } };
        }
        Val operator()(const Key &l, const Key &r) {
            return prod(l, r);
        }
        Val prod_by_key(const Key &l, const Key &r) {
            auto [new_root, res] = Node::prod_by_key(root, l, r);
            root = new_root;
            return res;
        }
        Val prod_by_index(int l, int r) {
            auto [new_root, res] = Node::prod_by_index(root, l, r);
            root = new_root;
            return res;
        }
        Val prod_all() {
            return Node::prod_all(root);
        }
        void apply_by_key(const Key &l, const Key &r, const F &f) {
            root = Node::apply_by_key(root, l, r, f);
        }
        void apply_by_index(int l, int r, const F &f) {
            root = Node::apply_by_index(root, l, r, f);
        }
        void apply_all(const F &f) {
            Node::apply_all(root, f);
        }

        Val get_or_default(const Key &key, const Val &default_value) {
            auto [new_root, res] = Node::get_or_default(root, key, default_value);
            root = new_root;
            return res;
        }
        std::pair<Key, Val> kth_entry(int k) {
            index_bounds_check(k, size());
            root = Node::splay_by_index(root, k);
            return { root->key, root->val };
        }
        LazyEvalMap split_by_index(int k) {
            index_bounds_check(k, size() + 1);
            auto [l, r] = Node::split_by_index(root, k);
            root = l;
            return LazyEvalMap(r);
        }
        LazyEvalMap split_by_key(const Key &key) {
            auto [l, r] = Node::split_by_key(root, key);
            root = l;
            return LazyEvalMap(r);
        }
        void merge(LazyEvalMap &&r) {
            assert(root != r.root);
            root = Node::merge(root, r.root);
            r.root = nullptr;
        }
        void swap(LazyEvalMap &r) {
            std::swap(root, r.root);
        }

    protected:
        Node *root;

        LazyEvalMap(node_ptr_t root) : root(root) {}
    
        static void index_bounds_check(unsigned int k, unsigned int n) {
            assert(k < n);
        }
        static void range_bounds_check(unsigned int l, unsigned int r, unsigned int n) {
            assert(l <= r and r <= n);
        }
};

}



#line 11 "test/src/datastructure/lazy_eval_map/leq_and_neq.test.cpp"

using suisen::CoordinateCompressorBuilder;
using suisen::LazyEvalMap;

struct S {
    mint sum;
    int len;
};
struct F {
    mint a, b;
};

S op(S x, S y) {
    return { x.sum + y.sum, x.len + y.len };
}
S e() {
    return { 0, 0 };
}
S mapping(F f, S x) {
    return { x.sum * f.a + x.len * f.b, x.len };
}
F composition(F f, F g) {
    return { f.a * g.a, f.a * g.b + f.b };
}
F id() {
    return { 1, 0 };
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int &e : a) std::cin >> e;
    CoordinateCompressorBuilder<int> builder(a);
    builder.push(0);
    auto comp = builder.build();
    int m = comp.size();
    LazyEvalMap<int, S, op, e, F, mapping, composition, id> mp;
    for (int i = 1; i < m; ++i) {
        int len = comp.decomp(i) - comp.decomp(i - 1);
        mp[i - 1] = { 0, len };
    }
    mint sum = 1;
    for (int v : a) {
        mp.apply_all({ -1, sum });
        mp.apply_by_key(comp[v], m, { 0, 0 });
        sum = mp.prod_all().sum;
    }
    std::cout << mp.prod_all().sum.val() << '\n';
    return 0;
}
Back to top page