test/range_reverse_range_sum_splay.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

• data_structure/splay_tree.hpp

Code

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

#include <data_structure/splay_tree.hpp>    // for SplayTree
#include <fastio/base.hpp>                  // for FASTIO, cin, cout
#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

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

    using splay = SplayTree<RSQ(ll, 0)>;
    splay::nptr root{nullptr};
    splay tree(a, root);
    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_splay.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_reverse_range_sum"

#include <data_structure/splay_tree.hpp>    // for SplayTree
#include <fastio/base.hpp>                  // for FASTIO, cin, cout
#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

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

    using splay = SplayTree<RSQ(ll, 0)>;
    splay::nptr root{nullptr};
    splay tree(a, root);
    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	760 ms	27 MB
g++	almost_t1_00	AC	711 ms	28 MB
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	781 ms	28 MB
g++	max_random_01	AC	774 ms	28 MB
g++	max_random_02	AC	779 ms	28 MB
g++	nq_01_00	AC	5 ms	4 MB
g++	nq_01_01	AC	4 ms	4 MB
g++	nq_01_02	AC	9 ms	5 MB
g++	nq_01_03	AC	4 ms	4 MB
g++	nq_01_04	AC	4 ms	4 MB
g++	nq_01_05	AC	8 ms	5 MB
g++	nq_01_06	AC	15 ms	15 MB
g++	nq_01_07	AC	17 ms	18 MB
g++	random_00	AC	680 ms	21 MB
g++	random_01	AC	482 ms	25 MB
g++	random_02	AC	703 ms	23 MB
g++	small_random_00	AC	274 ms	7 MB
g++	small_random_01	AC	151 ms	6 MB
g++	small_random_02	AC	215 ms	7 MB

Back to top page