hly1204's library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub hly1204/library

:heavy_check_mark: test/data_structure/range_affine_range_sum.1.test.cpp

Depends on

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_affine_range_sum

#include "avl_tree_node_base.hpp"
#include "modint.hpp"
#include "node_pool.hpp"
#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    using mint = ModInt<998244353>;
    struct AVLTreeNode : AVLTreeNodeBase<AVLTreeNode> {
        mint Val, Sum, Add, Mul = {1};
        void do_propagate() {
            if (left()) {
                left()->Add = Mul * left()->Add + Add;
                left()->Mul *= Mul;
                left()->Sum = Add * left()->size() + Mul * left()->Sum;
            }
            if (right()) {
                right()->Add = Mul * right()->Add + Add;
                right()->Mul *= Mul;
                right()->Sum = Add * right()->size() + Mul * right()->Sum;
            }
            Val = Add + Mul * Val;
            Add = 0;
            Mul = 1;
        }
        void do_update() {
            Sum = Val;
            if (left()) Sum += left()->Sum;
            if (right()) Sum += right()->Sum;
        }
    };
    int n, q;
    std::cin >> n >> q;
    FixedSizeNodePool<AVLTreeNode> pool(n);
    auto [node, id]   = pool.get_func();
    AVLTreeNode *root = nullptr;
    for (int i = 0; i < n; ++i) {
        std::cin >> node(i)->Val;
        node(i)->update();
        root = AVLTreeNode::join(root, node(i));
    }
    while (q--) {
        int cmd, l, r;
        std::cin >> cmd >> l >> r;
        auto [R0, R1, R2] = AVLTreeNode::split(root, l, r - l);
        if (cmd == 0) {
            std::cin >> R1->Mul >> R1->Add;
            R1->propagate();
            R1->update();
        } else {
            std::cout << R1->Sum << '\n';
        }
        root = AVLTreeNode::join(R0, R1, R2);
    }
    return 0;
}

#line 1 "test/data_structure/range_affine_range_sum.1.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_affine_range_sum

#line 2 "avl_tree_node_base.hpp"

#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <utility>

template<typename FlippableAVLTreeNodeT> class FlippableAVLTreeNodeBase;

template<typename AVLTreeNodeT> class AVLTreeNodeBase {
    friend class FlippableAVLTreeNodeBase<AVLTreeNodeT>;

    AVLTreeNodeBase *L;
    AVLTreeNodeBase *R;
    int Height;
    int Size;

    AVLTreeNodeT &underlying() { return (AVLTreeNodeT &)*this; }
    const AVLTreeNodeT &underlying() const { return (const AVLTreeNodeT &)*this; }

    // CRTP reimplement
    void do_propagate() {}
    void do_update() {}

    // base_propagate() is called to propagate the update information to child(ren).
    // There is no need to update the information combined from child(ren)
    // which should be done in base_update().
    void base_propagate() { underlying().do_propagate(); }
    // base_update() is called to update the information combined from child(ren).
    void base_update() {
        Size = 1;
        if (L) Size += L->Size;
        if (R) Size += R->Size;
        Height = std::max(L ? L->Height : 0, R ? R->Height : 0) + 1;
        underlying().do_update();
    }

    AVLTreeNodeBase *base_rotate_left() {
        /*    x              b
             / \            / \
            a   b    =>    x   d
               / \        / \
              c   d      a   c    */
        AVLTreeNodeBase *b = R;
        b->propagate(), R = b->L, b->L = this, update(), b->update();
        return b;
    }
    AVLTreeNodeBase *base_rotate_right() {
        /*    x              a
             / \            / \
            a   b    =>    c   x
           / \                / \
          c   d              d   b */
        AVLTreeNodeBase *a = L;
        a->propagate(), L = a->R, a->R = this, update(), a->update();
        return a;
    }

    enum class Child { LEFT, RIGHT };
    std::pair<AVLTreeNodeBase *, Child> taller_child() const {
        return (L ? L->Height : 0) > (R ? R->Height : 0) ? std::make_pair(L, Child::LEFT)
                                                         : std::make_pair(R, Child::RIGHT);
    }

    bool is_balanced() const { return std::abs((L ? L->Height : 0) - (R ? R->Height : 0)) <= 1; }

    AVLTreeNodeBase *balance() {
        if (is_balanced()) return this;
        auto [y, dy] = taller_child();
        if (dy == Child::LEFT) {
            if ((y->L ? y->L->Height : 0) < (y->R ? y->R->Height : 0))
                y->propagate(), L = y->base_rotate_left(), update();
            return base_rotate_right();
        }
        if ((y->L ? y->L->Height : 0) > (y->R ? y->R->Height : 0))
            y->propagate(), R = y->base_rotate_right(), update();
        return base_rotate_left();
    }

    std::array<AVLTreeNodeBase *, 2> extract_leftmost() {
        propagate();
        if (L == nullptr) {
            AVLTreeNodeBase *b = R;
            R                  = nullptr, update();
            return {b, this};
        }
        auto [l, e] = L->extract_leftmost();
        L           = l, update();
        return {balance(), e};
    }

    std::array<AVLTreeNodeBase *, 2> extract_rightmost() {
        propagate();
        if (R == nullptr) {
            AVLTreeNodeBase *b = L;
            L                  = nullptr, update();
            return {b, this};
        }
        auto [r, e] = R->extract_rightmost();
        R           = r, update();
        return {balance(), e};
    }

    // join(this, single, small)
    AVLTreeNodeBase *base_join_right(AVLTreeNodeBase *single, AVLTreeNodeBase *s) {
        assert(single != nullptr && single->L == nullptr && single->R == nullptr);
        assert(s != nullptr);
        assert(Height >= s->Height);
        propagate();
        if (Height - s->Height <= 1)
            return single->L = this, single->R = s, single->update(), single;
        return R = R->base_join_right(single, s), update(), balance();
    }

    // join(small, single, this)
    AVLTreeNodeBase *base_join_left(AVLTreeNodeBase *s, AVLTreeNodeBase *single) {
        assert(single != nullptr && single->L == nullptr && single->R == nullptr);
        assert(s != nullptr);
        assert(Height >= s->Height);
        propagate();
        if (Height - s->Height <= 1)
            return single->L = s, single->R = this, single->update(), single;
        return L = L->base_join_left(s, single), update(), balance();
    }

    // join(this, small)
    AVLTreeNodeBase *base_join_right(AVLTreeNodeBase *s) {
        assert(s != nullptr);
        assert(Height >= s->Height);
        propagate();
        if (Height - s->Height <= 1) {
            auto [r, e] = extract_rightmost();
            return e->L = r, e->R = s, e->update(), e;
        }
        return R = R->base_join_right(s), update(), balance();
    }

    // join(small, this)
    AVLTreeNodeBase *base_join_left(AVLTreeNodeBase *s) {
        assert(s != nullptr);
        assert(Height >= s->Height);
        propagate();
        if (Height - s->Height <= 1) {
            auto [r, e] = extract_leftmost();
            return e->L = s, e->R = r, e->update(), e;
        }
        return L = L->base_join_left(s), update(), balance();
    }

    static AVLTreeNodeBase *base_join(AVLTreeNodeBase *a, AVLTreeNodeBase *b) {
        if (a == nullptr) {
            if (b) b->propagate(), b->update();
            return b;
        }
        if (b == nullptr) {
            if (a) a->propagate(), a->update();
            return a;
        }
        if (a->Height >= b->Height) return b->propagate(), a->base_join_right(b);
        return a->propagate(), b->base_join_left(a);
    }

    static AVLTreeNodeBase *base_join(AVLTreeNodeBase *a, AVLTreeNodeBase *single,
                                      AVLTreeNodeBase *b) {
        assert(single != nullptr && single->L == nullptr && single->R == nullptr);
        if (a == nullptr) return base_join(single, b);
        if (b == nullptr) return base_join(a, single);
        if (a->Height >= b->Height) return b->propagate(), a->base_join_right(single, b);
        return a->propagate(), b->base_join_left(a, single);
    }

    static std::array<AVLTreeNodeBase *, 2> base_split(AVLTreeNodeBase *a, int k) {
        if (a == nullptr) return {nullptr, nullptr};
        a->propagate();
        if (k == 0) return {nullptr, a};
        if (k == a->Size) return {a, nullptr};
        const int leftsize = a->L != nullptr ? a->L->Size : 0;
        if (leftsize < k) {
            auto [b, c]        = base_split(a->R, k - leftsize - 1);
            AVLTreeNodeBase *l = a->L;
            a->L = a->R = nullptr, a->update();
            return {base_join(l, a, b), c};
        } else {
            auto [b, c]        = base_split(a->L, k);
            AVLTreeNodeBase *r = a->R;
            a->L = a->R = nullptr, a->update();
            return {b, base_join(c, a, r)};
        }
    }

protected:
    AVLTreeNodeBase() : L(), R(), Height(1), Size(1) {}

public:
    int size() const { return Size; }
    int height() const { return Height; }
    AVLTreeNodeT *left() const { return (AVLTreeNodeT *)L; }
    AVLTreeNodeT *right() const { return (AVLTreeNodeT *)R; }
    void update() { base_update(); }
    void propagate() { underlying().base_propagate(); }
    static AVLTreeNodeT *insert(AVLTreeNodeT *root, AVLTreeNodeT *t) {
        if (root == nullptr) return t;
        root->propagate();
        if (std::as_const(*t) < std::as_const(*root)) root->L = insert(root->left(), t);
        else { root->R = insert(root->right(), t); }
        return root->update(), (AVLTreeNodeT *)root->balance();
    }
    static int count_less_than(AVLTreeNodeT *root, const AVLTreeNodeT *t) {
        if (root == nullptr) return 0;
        root->propagate();
        if (std::as_const(*root) < *t)
            return (root->left() ? root->left()->size() : 0) + 1 +
                   count_less_than(root->right(), t);
        return count_less_than(root->left(), t);
    }
    static int count_less_equal(AVLTreeNodeT *root, const AVLTreeNodeT *t) {
        if (root == nullptr) return 0;
        root->propagate();
        if (*t < std::as_const(*root)) return count_less_equal(root->left(), t);
        return (root->left() ? root->left()->size() : 0) + 1 + count_less_equal(root->right(), t);
    }
    // [<, >=]
    static std::array<AVLTreeNodeT *, 2> split_less_than(AVLTreeNodeT *root,
                                                         const AVLTreeNodeT *t) {
        if (root == nullptr) return {nullptr, nullptr};
        root->propagate();
        if (std::as_const(*root) < *t) {
            auto [a, b] = split_less_than(root->right(), t);
            auto l      = root->L;
            root->L = root->R = nullptr, root->update();
            return {(AVLTreeNodeT *)base_join(l, root, a), b};
        }
        auto [a, b] = split_less_than(root->left(), t);
        auto r      = root->R;
        root->L = root->R = nullptr, root->update();
        return {a, (AVLTreeNodeT *)base_join(b, root, r)};
    }
    static int count_greater_than(AVLTreeNodeT *root, const AVLTreeNodeT *t) {
        if (root == nullptr) return 0;
        root->propagate();
        if (*t < std::as_const(*root))
            return (root->right() ? root->right()->size() : 0) + 1 +
                   count_greater_than(root->left(), t);
        return count_greater_than(root->right(), t);
    }
    static int count_greater_equal(AVLTreeNodeT *root, const AVLTreeNodeT *t) {
        if (root == nullptr) return 0;
        root->propagate();
        if (std::as_const(*root) < *t) return count_greater_equal(root->right(), t);
        return (root->right() ? root->right()->size() : 0) + 1 +
               count_greater_equal(root->left(), t);
    }
    // [<=, >]
    static std::array<AVLTreeNodeT *, 2> split_less_equal(AVLTreeNodeT *root,
                                                          const AVLTreeNodeT *t) {
        if (root == nullptr) return {nullptr, nullptr};
        root->propagate();
        if (*t < std::as_const(*root)) {
            auto [a, b] = split_less_equal(root->left(), t);
            auto r      = root->R;
            root->L = root->R = nullptr, root->update();
            return {a, (AVLTreeNodeT *)base_join(b, root, r)};
        }
        auto [a, b] = split_less_equal(root->right(), t);
        auto l      = root->L;
        root->L = root->R = nullptr, root->update();
        return {(AVLTreeNodeT *)base_join(l, root, a), b};
    }
    static int count(AVLTreeNodeT *root, const AVLTreeNodeT *t) {
        if (root == nullptr) return 0;
        root->propagate();
        if (*t < std::as_const(*root)) return count(root->left(), t);
        if (std::as_const(*root) < *t) return count(root->right(), t);
        int res = 1;
        if (root->left()) res += root->left()->size() - count_less_than(root->left(), t);
        if (root->right()) res += root->right()->size() - count_greater_than(root->right(), t);
        return res;
    }
    static bool contains(AVLTreeNodeT *root, const AVLTreeNodeT *t) {
        if (root == nullptr) return false;
        root->propagate();
        if (*t < std::as_const(*root)) return contains(root->left(), t);
        if (std::as_const(*root) < *t) return contains(root->right(), t);
        return true;
    }
    static std::array<int, 3> count3(AVLTreeNodeT *root, const AVLTreeNodeT *t) {
        if (root == nullptr) return {0, 0, 0};
        root->propagate();
        if (*t < std::as_const(*root)) {
            auto [a, b, c] = count3(root->left(), t);
            return {a, b, c + 1 + (root->right() ? root->right()->size() : 0)};
        }
        if (std::as_const(*root) < *t) {
            auto [a, b, c] = count3(root->right(), t);
            return {a + 1 + (root->left() ? root->left()->size() : 0), b, c};
        }
        const int a = count_less_than(root->left(), t);
        const int c = count_greater_than(root->right(), t);
        return {a, root->size() - a - c, c};
    }
    static std::array<AVLTreeNodeT *, 3> split3(AVLTreeNodeT *root, const AVLTreeNodeT *t) {
        if (root == nullptr) return {nullptr, nullptr, nullptr};
        root->propagate();
        if (*t < std::as_const(*root)) {
            auto [a, b, c] = split3(root->left(), t);
            auto r         = root->R;
            root->L = root->R = nullptr, root->update();
            return {a, b, (AVLTreeNodeT *)base_join(c, root, r)};
        }
        if (std::as_const(*root) < *t) {
            auto [a, b, c] = split3(root->right(), t);
            auto l         = root->L;
            root->L = root->R = nullptr, root->update();
            return {(AVLTreeNodeT *)base_join(l, root, a), b, c};
        }
        auto [a, b] = split_less_than(root->left(), t);
        auto [c, d] = split_less_equal(root->right(), t);
        root->L = root->R = nullptr, root->update();
        return {a, (AVLTreeNodeT *)base_join(b, root, c), d};
    }
    static AVLTreeNodeT *predecessor(AVLTreeNodeT *root, const AVLTreeNodeT *t) {
        AVLTreeNodeT *res = nullptr;
        while (root) {
            root->propagate();
            if (std::as_const(*root) < *t) {
                res = root, root = root->right();
            } else {
                root = root->left();
            }
        }
        return res;
    }
    static AVLTreeNodeT *successor(AVLTreeNodeT *root, const AVLTreeNodeT *t) {
        AVLTreeNodeT *res = nullptr;
        while (root) {
            root->propagate();
            if (*t < std::as_const(*root)) {
                res = root, root = root->left();
            } else {
                root = root->right();
            }
        }
        return res;
    }

    template<typename... Nodes> static AVLTreeNodeT *join(Nodes... root) {
        struct Helper {
            AVLTreeNodeBase *Val;
            Helper &operator|(AVLTreeNodeBase *A) {
                Val = base_join(Val, A);
                return *this;
            }
        } nil{nullptr};
        return (AVLTreeNodeT *)(nil | ... | root).Val;
    }
    template<typename... Parts> static std::array<AVLTreeNodeT *, sizeof...(Parts) + 1>
    split(AVLTreeNodeT *root, Parts... part) {
        std::array<AVLTreeNodeT *, sizeof...(Parts) + 1> res;
        res[0]    = root;
        int index = 0;
        (
            [&](int s) {
                auto [l, r]  = base_split(res[index], s);
                res[index]   = (AVLTreeNodeT *)l;
                res[++index] = (AVLTreeNodeT *)r;
            }(part),
            ...);
        return res;
    }

    static AVLTreeNodeT *find(AVLTreeNodeT *root, const AVLTreeNodeT *t) {
        if (root == nullptr) return nullptr;
        root->propagate();
        if (std::as_const(*root) < *t) return find(root->right(), t);
        if (*t < std::as_const(*root)) return find(root->left(), t);
        return root;
    }

    AVLTreeNodeT *select(int k) {
        propagate();
        const int leftsize = left() ? left()->size() : 0;
        if (k == leftsize) return (AVLTreeNodeT *)this;
        if (k < leftsize) return left()->select(k);
        return right()->select(k - leftsize - 1);
    }
};

template<typename FlippableAVLTreeNodeT> class FlippableAVLTreeNodeBase
    : public AVLTreeNodeBase<FlippableAVLTreeNodeT> {
    friend class AVLTreeNodeBase<FlippableAVLTreeNodeT>;

    bool NeedFlip;

    FlippableAVLTreeNodeT &underlying() { return (FlippableAVLTreeNodeT &)*this; }
    const FlippableAVLTreeNodeT &underlying() const { return (const FlippableAVLTreeNodeT &)*this; }

    // CRTP reimplement
    void do_flip() {}

    void base_flip() {
        NeedFlip = !NeedFlip;
        std::swap(this->L, this->R);
        underlying().do_flip();
    }
    void base_propagate() {
        underlying().do_propagate();
        if (NeedFlip) {
            NeedFlip = false;
            if (this->left()) this->left()->underlying().base_flip();
            if (this->right()) this->right()->underlying().base_flip();
        }
    }

protected:
    FlippableAVLTreeNodeBase() : NeedFlip() {}

public:
    void flip() { base_flip(); }
};
#line 2 "modint.hpp"

#include <iostream>
#include <type_traits>

// clang-format off
template<unsigned Mod> class ModInt {
    static_assert((Mod >> 31) == 0, "`Mod` must less than 2^(31)");
    template<typename Int>
    static std::enable_if_t<std::is_integral_v<Int>, unsigned> safe_mod(Int v) { using D = std::common_type_t<Int, unsigned>; return (v %= (int)Mod) < 0 ? (D)(v + (int)Mod) : (D)v; }
    struct PrivateConstructor {} static inline private_constructor{};
    ModInt(PrivateConstructor, unsigned v) : v_(v) {}
    unsigned v_;

public:
    static unsigned mod() { return Mod; }
    static ModInt from_raw(unsigned v) { return ModInt(private_constructor, v); }
    static ModInt zero() { return from_raw(0); }
    static ModInt one() { return from_raw(1); }
    bool is_zero() const { return v_ == 0; }
    bool is_one() const { return v_ == 1; }
    ModInt() : v_() {}
    template<typename Int, typename std::enable_if_t<std::is_signed_v<Int>, int> = 0> ModInt(Int v) : v_(safe_mod(v)) {}
    template<typename Int, typename std::enable_if_t<std::is_unsigned_v<Int>, int> = 0> ModInt(Int v) : v_(v % Mod) {}
    unsigned val() const { return v_; }
    ModInt operator-() const { return from_raw(v_ == 0 ? v_ : Mod - v_); }
    ModInt pow(long long e) const { if (e < 0) return inv().pow(-e); for (ModInt x(*this), res(from_raw(1));; x *= x) { if (e & 1) res *= x; if ((e >>= 1) == 0) return res; }}
    ModInt inv() const { int x1 = 1, x3 = 0, a = val(), b = Mod; while (b) { const int q = a / b, x1_old = x1, a_old = a; x1 = x3, x3 = x1_old - x3 * q, a = b, b = a_old - b * q; } return from_raw(x1 < 0 ? x1 + (int)Mod : x1); }
    template<bool Odd = (Mod & 1)> std::enable_if_t<Odd, ModInt> div_by_2() const { if (v_ & 1) return from_raw((v_ + Mod) >> 1); return from_raw(v_ >> 1); }
    ModInt &operator+=(const ModInt &a) { if ((v_ += a.v_) >= Mod) v_ -= Mod; return *this; }
    ModInt &operator-=(const ModInt &a) { if ((v_ += Mod - a.v_) >= Mod) v_ -= Mod; return *this; }
    ModInt &operator*=(const ModInt &a) { v_ = (unsigned long long)v_ * a.v_ % Mod; return *this; }
    ModInt &operator/=(const ModInt &a) { return *this *= a.inv(); }
    ModInt &operator++() { return *this += one(); }
    ModInt operator++(int) { ModInt o(*this); *this += one(); return o; }
    ModInt &operator--() { return *this -= one(); }
    ModInt operator--(int) { ModInt o(*this); *this -= one(); return o; }
    friend ModInt operator+(const ModInt &a, const ModInt &b) { return ModInt(a) += b; }
    friend ModInt operator-(const ModInt &a, const ModInt &b) { return ModInt(a) -= b; }
    friend ModInt operator*(const ModInt &a, const ModInt &b) { return ModInt(a) *= b; }
    friend ModInt operator/(const ModInt &a, const ModInt &b) { return ModInt(a) /= b; }
    friend bool operator==(const ModInt &a, const ModInt &b) { return a.v_ == b.v_; }
    friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v_ != b.v_; }
    friend std::istream &operator>>(std::istream &a, ModInt &b) { int v; a >> v; b.v_ = safe_mod(v); return a; }
    friend std::ostream &operator<<(std::ostream &a, const ModInt &b) { return a << b.val(); }
};
// clang-format on
#line 2 "node_pool.hpp"

#include <list>
#include <memory>
#line 6 "node_pool.hpp"
#include <vector>

template<typename NodeT> class FixedSizeNodePool {
    std::vector<NodeT> pool;

public:
    explicit FixedSizeNodePool(int n) : pool(n) {}
    NodeT *at(int ind) { return pool.data() + ind; }
    int id(NodeT *a) const { return a - pool.data(); }
    auto get_func() {
        return std::make_pair([this](int ind) { return at(ind); },
                              [this](NodeT *a) { return id(a); });
    }
};

template<typename NodeT> class DynamicSizeNodePool {
    struct Wrapped : public NodeT {
        using NodeT::NodeT;
        typename std::list<Wrapped>::iterator i;
    };
    std::list<Wrapped> used_list;
    std::list<Wrapped> free_list;

public:
    template<typename... Args> NodeT *make(Args &&...arg) {
        if (free_list.empty()) {
            auto &&node = used_list.emplace_back(std::forward<Args>(arg)...);
            node.i      = std::prev(used_list.end());
            return std::addressof(node);
        }
        used_list.splice(used_list.end(), free_list, std::prev(free_list.end()));
        auto &&node = used_list.back();
        node.~NodeT(); // i remains unchanged
        new (std::addressof(node)) NodeT(std::forward<Args>(arg)...);
        return std::addressof(node);
    }
    // this is lazy, if sth. relies on the order of dtor, do NOT use
    void retrieve(NodeT *node) {
        free_list.splice(free_list.end(), used_list, ((Wrapped *)node)->i);
    }
};
#line 7 "test/data_structure/range_affine_range_sum.1.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    using mint = ModInt<998244353>;
    struct AVLTreeNode : AVLTreeNodeBase<AVLTreeNode> {
        mint Val, Sum, Add, Mul = {1};
        void do_propagate() {
            if (left()) {
                left()->Add = Mul * left()->Add + Add;
                left()->Mul *= Mul;
                left()->Sum = Add * left()->size() + Mul * left()->Sum;
            }
            if (right()) {
                right()->Add = Mul * right()->Add + Add;
                right()->Mul *= Mul;
                right()->Sum = Add * right()->size() + Mul * right()->Sum;
            }
            Val = Add + Mul * Val;
            Add = 0;
            Mul = 1;
        }
        void do_update() {
            Sum = Val;
            if (left()) Sum += left()->Sum;
            if (right()) Sum += right()->Sum;
        }
    };
    int n, q;
    std::cin >> n >> q;
    FixedSizeNodePool<AVLTreeNode> pool(n);
    auto [node, id]   = pool.get_func();
    AVLTreeNode *root = nullptr;
    for (int i = 0; i < n; ++i) {
        std::cin >> node(i)->Val;
        node(i)->update();
        root = AVLTreeNode::join(root, node(i));
    }
    while (q--) {
        int cmd, l, r;
        std::cin >> cmd >> l >> r;
        auto [R0, R1, R2] = AVLTreeNode::split(root, l, r - l);
        if (cmd == 0) {
            std::cin >> R1->Mul >> R1->Add;
            R1->propagate();
            R1->update();
        } else {
            std::cout << R1->Sum << '\n';
        }
        root = AVLTreeNode::join(R0, R1, R2);
    }
    return 0;
}

Test cases

Env Name Status Elapsed Memory
clang++ example_00 :heavy_check_mark: AC 10 ms 22 MB
clang++ max_random_00 :heavy_check_mark: AC 6369 ms 44 MB
clang++ max_random_01 :heavy_check_mark: AC 6298 ms 42 MB
clang++ max_random_02 :heavy_check_mark: AC 6341 ms 42 MB
clang++ random_00 :heavy_check_mark: AC 5021 ms 37 MB
clang++ random_01 :heavy_check_mark: AC 5177 ms 40 MB
clang++ random_02 :heavy_check_mark: AC 3009 ms 24 MB
clang++ small_00 :heavy_check_mark: AC 10 ms 20 MB
clang++ small_01 :heavy_check_mark: AC 9 ms 24 MB
clang++ small_02 :heavy_check_mark: AC 10 ms 22 MB
clang++ small_03 :heavy_check_mark: AC 10 ms 24 MB
clang++ small_04 :heavy_check_mark: AC 10 ms 22 MB
clang++ small_05 :heavy_check_mark: AC 10 ms 22 MB
clang++ small_06 :heavy_check_mark: AC 10 ms 20 MB
clang++ small_07 :heavy_check_mark: AC 10 ms 20 MB
clang++ small_08 :heavy_check_mark: AC 10 ms 23 MB
clang++ small_09 :heavy_check_mark: AC 10 ms 20 MB
clang++ small_random_00 :heavy_check_mark: AC 15 ms 22 MB
clang++ small_random_01 :heavy_check_mark: AC 13 ms 22 MB
Back to top page