test/data_structure/range_reverse_range_sum.0.test.cpp

View this file on GitHub
Last update: 2025-01-19 15:28:01+08:00
Problem: https://judge.yosupo.jp/problem/range_reverse_range_sum

Depends on

Code

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

#include "treap_node_base.hpp"
#include <iostream>
#include <memory>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    struct TreapNode : TreapNodeBase<TreapNode> {
        int Val;
        long long Sum;
        void do_update() {
            Sum = Val;
            if (left()) Sum += left()->Sum;
            if (right()) Sum += right()->Sum;
        }
    };
    int n, q;
    std::cin >> n >> q;
    auto buf        = std::make_unique<TreapNode[]>(n);
    TreapNode *root = nullptr;
    for (int i = 0; i < n; ++i) {
        std::cin >> buf[i].Val;
        root = TreapNode::join(root, &buf[i]);
    }
    while (q--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        auto [a, b, c] = TreapNode::split(root, l, r - l);
        if (t == 0) {
            if (b) b->flip();
        } else {
            std::cout << (b ? b->Sum : 0LL) << '\n';
        }
        root = TreapNode::join(a, b, c);
    }
    return 0;
}

#line 1 "test/data_structure/range_reverse_range_sum.0.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_reverse_range_sum"

#line 2 "treap_node_base.hpp"

#line 2 "rng.hpp"

#include <cstdint>
#include <limits>

// see: https://prng.di.unimi.it/xoshiro256starstar.c
// original license CC0 1.0
class xoshiro256starstar {
    using u64 = std::uint64_t;

    static inline u64 rotl(const u64 x, int k) { return (x << k) | (x >> (64 - k)); }

    u64 s_[4];

    u64 next() {
        const u64 res = rotl(s_[1] * 5, 7) * 9;
        const u64 t   = s_[1] << 17;
        s_[2] ^= s_[0];
        s_[3] ^= s_[1];
        s_[1] ^= s_[2];
        s_[0] ^= s_[3];
        s_[2] ^= t;
        s_[3] = rotl(s_[3], 45);
        return res;
    }

public:
    // see: https://prng.di.unimi.it/splitmix64.c
    // original license CC0 1.0
    explicit xoshiro256starstar(u64 seed) {
        for (int i = 0; i < 4; ++i) {
            u64 z = (seed += 0x9e3779b97f4a7c15);
            z     = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
            z     = (z ^ (z >> 27)) * 0x94d049bb133111eb;
            s_[i] = z ^ (z >> 31);
        }
    }
    // see: https://en.cppreference.com/w/cpp/named_req/UniformRandomBitGenerator
    using result_type = u64;
    static constexpr u64 min() { return std::numeric_limits<u64>::min(); }
    static constexpr u64 max() { return std::numeric_limits<u64>::max(); }
    u64 operator()() { return next(); }
};
#line 4 "treap_node_base.hpp"
#include <array>
#include <random>
#include <utility>

template<typename TreapNode> class TreapNodeBase {
    TreapNodeBase *L;
    TreapNodeBase *R;
    int Rank;
    int Size;
    bool NeedFlip;

    static inline xoshiro256starstar gen{std::random_device{}()};
    static inline std::uniform_int_distribution<int> dis{0, 998244353};

    TreapNode *derived() { return (TreapNode *)this; }

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

protected:
    void base_flip() {
        NeedFlip = !NeedFlip;
        std::swap(L, R);
        derived()->do_flip();
    }
    // 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() {
        derived()->do_propagate();
        if (NeedFlip) {
            NeedFlip = false;
            if (L) L->base_flip();
            if (R) R->base_flip();
        }
    }
    // 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;
        derived()->do_update();
    }

    static TreapNodeBase *base_join(TreapNodeBase *a, TreapNodeBase *b) {
        if (a == nullptr) {
            if (b) b->base_propagate(), b->base_update();
            return b;
        }
        if (b == nullptr) {
            if (a) a->base_propagate(), a->base_update();
            return a;
        }
        a->base_propagate();
        b->base_propagate();
        if (a->Rank < b->Rank) {
            b->L = base_join(a, b->L);
            b->base_update();
            return b;
        }
        a->R = base_join(a->R, b);
        a->base_update();
        return a;
    }

    static std::array<TreapNodeBase *, 2> base_split(TreapNodeBase *a, int k) {
        if (a == nullptr) return {nullptr, nullptr};
        a->base_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);
            a->R        = b;
            a->base_update();
            return {a, c};
        }
        auto [b, c] = base_split(a->L, k);
        a->L        = c;
        a->base_update();
        return {b, a};
    }

    TreapNodeBase() : L(), R(), Rank(dis(gen)), Size(1), NeedFlip() {}

public:
    int size() const { return Size; }
    int rank() const { return Rank; }

    TreapNode *left() const { return (TreapNode *)L; }
    TreapNode *right() const { return (TreapNode *)R; }

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

    TreapNode *select(int k) {
        base_propagate();
        const int leftsize = left() ? left()->size() : 0;
        if (k == leftsize) return (TreapNode *)this;
        if (k < leftsize) return left()->select(k);
        return right()->select(k - leftsize - 1);
    }
};
#line 4 "test/data_structure/range_reverse_range_sum.0.test.cpp"
#include <iostream>
#include <memory>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    struct TreapNode : TreapNodeBase<TreapNode> {
        int Val;
        long long Sum;
        void do_update() {
            Sum = Val;
            if (left()) Sum += left()->Sum;
            if (right()) Sum += right()->Sum;
        }
    };
    int n, q;
    std::cin >> n >> q;
    auto buf        = std::make_unique<TreapNode[]>(n);
    TreapNode *root = nullptr;
    for (int i = 0; i < n; ++i) {
        std::cin >> buf[i].Val;
        root = TreapNode::join(root, &buf[i]);
    }
    while (q--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        auto [a, b, c] = TreapNode::split(root, l, r - l);
        if (t == 0) {
            if (b) b->flip();
        } else {
            std::cout << (b ? b->Sum : 0LL) << '\n';
        }
        root = TreapNode::join(a, b, c);
    }
    return 0;
}