Library

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

View the Project on GitHub ebi-fly13/Library

:heavy_check_mark: test/data_structure/Dynamic_Sequence_Range_Affine_Range_Sum.test.cpp

Depends on

Code

#define PROBLEM \
    "https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum"

#include <iostream>


#include "../../data_structure/ImplicitTreap.hpp"

#include "../../modint/modint.hpp"

#include "../../template/int_alias.hpp"


using mint = ebi::modint998244353;

struct S {
    mint a;
    int size;
};

struct F {
    mint a, b;
    F(mint a, mint b) : a(a), b(b) {}
};

S op(S l, S r) {
    return S{l.a + r.a, l.size + r.size};
}

S e() {
    return S{0, 0};
}

S mapping(F l, S r) {
    return S{r.a * l.a + (mint)r.size * l.b, r.size};
}

F composition(F l, F r) {
    return F{r.a * l.a, r.b * l.a + l.b};
}

F id() {
    return F{1, 0};
}

using ebi::i64;

int main() {
    ebi::ImplicitTreap<S, op, e, F, mapping, composition, id> treap;
    int n, q;
    std::cin >> n >> q;
    for (int i = 0; i < n; i++) {
        i64 a;
        std::cin >> a;
        treap.insert(i, {a, 1});
    }
    while (q--) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int i;
            i64 x;
            std::cin >> i >> x;
            treap.insert(i, {x, 1});
        } else if (t == 1) {
            int i;
            std::cin >> i;
            treap.erase(i);
        } else if (t == 2) {
            int l, r;
            std::cin >> l >> r;
            treap.reverse(l, r);
        } else if (t == 3) {
            int l, r, b, c;
            std::cin >> l >> r >> b >> c;
            treap.apply(l, r, F(b, c));
        } else if (t == 4) {
            int l, r;
            std::cin >> l >> r;
            std::cout << treap.prod(l, r).a.value() << std::endl;
        }
    }
}
#line 1 "test/data_structure/Dynamic_Sequence_Range_Affine_Range_Sum.test.cpp"
#define PROBLEM \
    "https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum"

#include <iostream>


#line 2 "data_structure/ImplicitTreap.hpp"

/*
    reference: https://www.slideshare.net/iwiwi/2-12188757
               実装方法やTreapのアイデアなど.
               https://xuzijian629.hatenablog.com/entry/2018/12/08/000452
               Treapをリストのように扱う方法や実装法, Monoidの載せ方など.
*/

#include <random>


namespace ebi {

template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S),
          F (*composition)(F, F), F (*id)()>
struct ImplicitTreap {
  private:
    struct Node {
        S val, acc;
        F lazy;
        int pri, cnt;
        bool rev;
        Node *lch, *rch;
        Node(S val, int pri)
            : val(val),
              acc(e()),
              lazy(id()),
              pri(pri),
              cnt(0),
              rev(false),
              lch(nullptr),
              rch(nullptr) {}
    };

    using node_ptr = Node *;

    node_ptr root;

    std::random_device rnd;
    std::mt19937 mt;
    std::uniform_int_distribution<> pri_rnd;

    int cnt(node_ptr t) {
        return t ? t->cnt : 0;
    }

    void update_cnt(node_ptr t) {
        if (t) {
            t->cnt = 1 + cnt(t->lch) + cnt(t->rch);
        }
    }

    S acc(node_ptr t) {
        return t ? t->acc : e();
    }

    void update_acc(node_ptr t) {
        if (t) {
            t->acc = op(acc(t->lch), t->val);
            t->acc = op(t->acc, acc(t->rch));
        }
    }

    void eval(node_ptr t) {
        if (t) {
            if (t->lch) {
                t->lch->lazy = composition(t->lazy, t->lch->lazy);
                t->lch->acc = mapping(t->lazy, t->lch->acc);
            }
            if (t->rch) {
                t->rch->lazy = composition(t->lazy, t->rch->lazy);
                t->rch->acc = mapping(t->lazy, t->rch->acc);
            }
            t->val = mapping(t->lazy, t->val);
            t->lazy = id();
        }
    }

    void pushdown(node_ptr t) {
        if (t && t->rev) {
            t->rev = false;
            std::swap(t->lch, t->rch);
            if (t->lch) t->lch->rev ^= 1;
            if (t->rch) t->rch->rev ^= 1;
        }
        eval(t);
        update(t);
    }

    void update(node_ptr t) {
        update_cnt(t);
        update_acc(t);
    }

    node_ptr merge(node_ptr l, node_ptr r) {
        pushdown(l);
        pushdown(r);
        if (!l || !r) {
            return !l ? r : l;
        }
        if (l->pri > r->pri) {
            l->rch = merge(l->rch, r);
            update(l);
            return l;
        } else {
            r->lch = merge(l, r->lch);
            update(r);
            return r;
        }
    }

    std::pair<node_ptr, node_ptr> split(node_ptr t, int key) {
        if (!t) return std::pair<node_ptr, node_ptr>(nullptr, nullptr);
        pushdown(t);
        if (key < cnt(t->lch) + 1) {
            auto [l, r] = split(t->lch, key);
            t->lch = r;
            update(t);
            return std::pair<node_ptr, node_ptr>(l, t);
        } else {
            auto [l, r] = split(t->rch, key - cnt(t->lch) - 1);
            t->rch = l;
            update(t);
            return std::pair<node_ptr, node_ptr>(t, r);
        }
    }

  public:
    ImplicitTreap() : root(nullptr) {
        mt = std::mt19937(rnd());
        pri_rnd = std::uniform_int_distribution<>(0, 1e9);
    }

    void insert(int k, S x) {
        auto [l, r] = split(root, k);
        auto t = merge(l, new Node(x, pri_rnd(mt)));
        root = merge(t, r);
    }

    void erase(int k) {
        auto [l, r] = split(root, k + 1);
        auto [nl, nr] = split(l, k);
        root = merge(nl, r);
    }

    void reverse(int l, int r) {
        auto [t1, t2] = split(root, l);
        auto [t3, t4] = split(t2, r - l);
        t3->rev ^= 1;
        t1 = merge(t1, t3);
        root = merge(t1, t4);
    }

    void apply(int l, int r, F x) {
        auto [t1, t2] = split(root, l);
        auto [t3, t4] = split(t2, r - l);
        t3->lazy = composition(x, t3->lazy);
        t3->acc = mapping(x, t3->acc);
        t1 = merge(t1, t3);
        root = merge(t1, t4);
    }

    S prod(int l, int r) {
        auto [t1, t2] = split(root, l);
        auto [t3, t4] = split(t2, r - l);
        S ret = t3->acc;
        t1 = merge(t1, t3);
        root = merge(t1, t4);
        return ret;
    }
};

}  // namespace ebi
#line 2 "modint/modint.hpp"

#include <cassert>

#line 5 "modint/modint.hpp"

#line 2 "modint/base.hpp"

#include <concepts>
#line 5 "modint/base.hpp"
#include <utility>

namespace ebi {

template <class T>
concept Modint = requires(T a, T b) {
    a + b;
    a - b;
    a * b;
    a / b;
    a.inv();
    a.val();
    a.pow(std::declval<long long>());
    T::mod();
};

template <Modint mint> std::istream &operator>>(std::istream &os, mint &a) {
    long long x;
    os >> x;
    a = x;
    return os;
}

template <Modint mint>
std::ostream &operator<<(std::ostream &os, const mint &a) {
    return os << a.val();
}

}  // namespace ebi
#line 7 "modint/modint.hpp"

namespace ebi {

template <int m> struct static_modint {
  private:
    using modint = static_modint;

  public:
    static constexpr int mod() {
        return m;
    }

    static constexpr modint raw(int v) {
        modint x;
        x._v = v;
        return x;
    }

    constexpr static_modint() : _v(0) {}

    template <std::signed_integral T> constexpr static_modint(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }

    template <std::unsigned_integral T> constexpr static_modint(T v) {
        _v = (unsigned int)(v % umod());
    }

    constexpr unsigned int val() const {
        return _v;
    }

    constexpr unsigned int value() const {
        return val();
    }

    constexpr modint &operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    constexpr modint &operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }

    constexpr modint operator++(int) {
        modint res = *this;
        ++*this;
        return res;
    }
    constexpr modint operator--(int) {
        modint res = *this;
        --*this;
        return res;
    }

    constexpr modint &operator+=(const modint &rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    constexpr modint &operator-=(const modint &rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    constexpr modint &operator*=(const modint &rhs) {
        unsigned long long x = _v;
        x *= rhs._v;
        _v = (unsigned int)(x % (unsigned long long)umod());
        return *this;
    }
    constexpr modint &operator/=(const modint &rhs) {
        return *this = *this * rhs.inv();
    }

    constexpr modint operator+() const {
        return *this;
    }
    constexpr modint operator-() const {
        return modint() - *this;
    }

    constexpr modint pow(long long n) const {
        assert(0 <= n);
        modint x = *this, res = 1;
        while (n) {
            if (n & 1) res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
    constexpr modint inv() const {
        assert(_v);
        return pow(umod() - 2);
    }

    friend modint operator+(const modint &lhs, const modint &rhs) {
        return modint(lhs) += rhs;
    }
    friend modint operator-(const modint &lhs, const modint &rhs) {
        return modint(lhs) -= rhs;
    }
    friend modint operator*(const modint &lhs, const modint &rhs) {
        return modint(lhs) *= rhs;
    }

    friend modint operator/(const modint &lhs, const modint &rhs) {
        return modint(lhs) /= rhs;
    }
    friend bool operator==(const modint &lhs, const modint &rhs) {
        return lhs.val() == rhs.val();
    }
    friend bool operator!=(const modint &lhs, const modint &rhs) {
        return !(lhs == rhs);
    }

  private:
    unsigned int _v = 0;

    static constexpr unsigned int umod() {
        return m;
    }
};

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;

}  // namespace ebi
#line 2 "template/int_alias.hpp"

#include <cstdint>

namespace ebi {

using ld = long double;
using std::size_t;
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

}  // namespace ebi
#line 9 "test/data_structure/Dynamic_Sequence_Range_Affine_Range_Sum.test.cpp"

using mint = ebi::modint998244353;

struct S {
    mint a;
    int size;
};

struct F {
    mint a, b;
    F(mint a, mint b) : a(a), b(b) {}
};

S op(S l, S r) {
    return S{l.a + r.a, l.size + r.size};
}

S e() {
    return S{0, 0};
}

S mapping(F l, S r) {
    return S{r.a * l.a + (mint)r.size * l.b, r.size};
}

F composition(F l, F r) {
    return F{r.a * l.a, r.b * l.a + l.b};
}

F id() {
    return F{1, 0};
}

using ebi::i64;

int main() {
    ebi::ImplicitTreap<S, op, e, F, mapping, composition, id> treap;
    int n, q;
    std::cin >> n >> q;
    for (int i = 0; i < n; i++) {
        i64 a;
        std::cin >> a;
        treap.insert(i, {a, 1});
    }
    while (q--) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int i;
            i64 x;
            std::cin >> i >> x;
            treap.insert(i, {x, 1});
        } else if (t == 1) {
            int i;
            std::cin >> i;
            treap.erase(i);
        } else if (t == 2) {
            int l, r;
            std::cin >> l >> r;
            treap.reverse(l, r);
        } else if (t == 3) {
            int l, r, b, c;
            std::cin >> l >> r >> b >> c;
            treap.apply(l, r, F(b, c));
        } else if (t == 4) {
            int l, r;
            std::cin >> l >> r;
            std::cout << treap.prod(l, r).a.value() << std::endl;
        }
    }
}
Back to top page