test/range_reverse_range_sum.test.cpp

• View this file on GitHub
• Last update: 2025-05-28 17:58:43+09:00
• Problem: https://judge.yosupo.jp/problem/range_reverse_range_sum

Depends on

• Randomized Binary Search Tree (data_structure/randomized_binary_search_tree.hpp)

Code

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

#include <data_structure/randomized_binary_search_tree.hpp>  // for Randomiz...
#include <fastio/base.hpp>                                   // for FASTIO, cin
#include <fastio/char/write.hpp>                             // for operator<<
#include <fastio/signed/read.hpp>                            // for operator>>
#include <fastio/signed/write.hpp>                           // for operator<<
#include <fastio/vector/read.hpp>                            // for operator>>
#include <templates/macro/abbrev/endl.hpp>                   // for endl
#include <templates/macro/abbrev/ll.hpp>                     // for ll
#include <templates/macro/segtree/RSQ.hpp>                   // for RSQ
#include <templates/rep.hpp>                                 // for rep
#include <templates/template.hpp>
#include <vector>  // for vector
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    cin >> a;

    using rbst = RandomizedBinarySearchTree<RSQ(ll, 0)>;
    rbst tree;
    rbst::nptr root{nullptr};
    rep(i, n) {
        tree.insert(root, i, a[i]);
    }
    rep(_, q) {
        ll T, l, r;
        cin >> T >> l >> r;
        if (T == 0) {
            tree.reverse(root, l, r);
        } else {
            auto ans = tree(root, l, r);
            cout << ans << endl;
        }
    }
}

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

#include <data_structure/randomized_binary_search_tree.hpp>  // for Randomiz...
#include <fastio/base.hpp>                                   // for FASTIO, cin
#include <fastio/char/write.hpp>                             // for operator<<
#include <fastio/signed/read.hpp>                            // for operator>>
#include <fastio/signed/write.hpp>                           // for operator<<
#include <fastio/vector/read.hpp>                            // for operator>>
#include <templates/macro/abbrev/endl.hpp>                   // for endl
#include <templates/macro/abbrev/ll.hpp>                     // for ll
#include <templates/macro/segtree/RSQ.hpp>                   // for RSQ
#include <templates/rep.hpp>                                 // for rep
#include <templates/template.hpp>
#include <vector>  // for vector
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    cin >> a;

    using rbst = RandomizedBinarySearchTree<RSQ(ll, 0)>;
    rbst tree;
    rbst::nptr root{nullptr};
    rep(i, n) {
        tree.insert(root, i, a[i]);
    }
    rep(_, q) {
        ll T, l, r;
        cin >> T >> l >> r;
        if (T == 0) {
            tree.reverse(root, l, r);
        } else {
            auto ans = tree(root, l, r);
            cout << ans << endl;
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_t0_00	AC	3361 ms	25 MB
g++	almost_t1_00	AC	2749 ms	25 MB
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	3132 ms	25 MB
g++	max_random_01	AC	3126 ms	26 MB
g++	max_random_02	AC	3146 ms	26 MB
g++	nq_01_00	AC	5 ms	4 MB
g++	nq_01_01	AC	5 ms	4 MB
g++	nq_01_02	AC	15 ms	5 MB
g++	nq_01_03	AC	5 ms	4 MB
g++	nq_01_04	AC	4 ms	4 MB
g++	nq_01_05	AC	26 ms	5 MB
g++	nq_01_06	AC	297 ms	13 MB
g++	nq_01_07	AC	379 ms	16 MB
g++	random_00	AC	2642 ms	19 MB
g++	random_01	AC	2052 ms	22 MB
g++	random_02	AC	2800 ms	21 MB
g++	small_random_00	AC	999 ms	7 MB
g++	small_random_01	AC	549 ms	6 MB
g++	small_random_02	AC	804 ms	7 MB

Back to top page