test/point_set_range_composite_large_array.test.cpp

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

Depends on

• Dynamic Segment Tree (data_structure/dynamic_segment_tree.hpp)

Code

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

#include <sys/types.h>  // for uint

#include <data_structure/dynamic_segment_tree.hpp>  // for DynamicSegmentTree
#include <fastio/base.hpp>                          // for FASTIO, cin, cout
#include <fastio/char/write.hpp>                    // for operator<<
#include <fastio/signed/read.hpp>                   // for operator>>
#include <fastio/unsigned/read.hpp>                 // for operator>>
#include <fastio/unsigned/write.hpp>                // for operator<<
#include <iterator>                                 // for pair
#include <templates/macro/abbrev/endl.hpp>          // for endl
#include <templates/macro/abbrev/mp.hpp>            // for MP
#include <templates/macro/abbrev/ull.hpp>           // for ull
#include <templates/macro/mod.hpp>                  // for MOD1
#include <templates/rep.hpp>                        // for rep
#include <templates/template.hpp>
#include <utility>  // for pair, make_pair
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    DynamicSegmentTree<
        pair<ull, ull>,
        [](pair<ull, ull> a, pair<ull, ull> b) {
            return MP(a.first * b.first % MOD1, (a.second * b.first + b.second) % MOD1);
        },
        []() -> pair<ull, ull> { return MP(1, 0); }>
        seg;
    rep(_, q) {
        uint T;
        ull l, r, x;
        cin >> T >> l >> r >> x;
        if (T == 0) {
            seg.set(l, {r, x});
        } else {
            auto res = seg(l, r);
            auto ans = (res.first * x + res.second) % MOD1;
            cout << ans << endl;
        }
    }
}

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

#include <sys/types.h>  // for uint

#include <data_structure/dynamic_segment_tree.hpp>  // for DynamicSegmentTree
#include <fastio/base.hpp>                          // for FASTIO, cin, cout
#include <fastio/char/write.hpp>                    // for operator<<
#include <fastio/signed/read.hpp>                   // for operator>>
#include <fastio/unsigned/read.hpp>                 // for operator>>
#include <fastio/unsigned/write.hpp>                // for operator<<
#include <iterator>                                 // for pair
#include <templates/macro/abbrev/endl.hpp>          // for endl
#include <templates/macro/abbrev/mp.hpp>            // for MP
#include <templates/macro/abbrev/ull.hpp>           // for ull
#include <templates/macro/mod.hpp>                  // for MOD1
#include <templates/rep.hpp>                        // for rep
#include <templates/template.hpp>
#include <utility>  // for pair, make_pair
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    DynamicSegmentTree<
        pair<ull, ull>,
        [](pair<ull, ull> a, pair<ull, ull> b) {
            return MP(a.first * b.first % MOD1, (a.second * b.first + b.second) % MOD1);
        },
        []() -> pair<ull, ull> { return MP(1, 0); }>
        seg;
    rep(_, q) {
        uint T;
        ull l, r, x;
        cin >> T >> l >> r >> x;
        if (T == 0) {
            seg.set(l, {r, x});
        } else {
            auto res = seg(l, r);
            auto ans = (res.first * x + res.second) % MOD1;
            cout << ans << endl;
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	dense_00	AC	87 ms	22 MB
g++	dense_01	AC	2183 ms	23 MB
g++	dense_02	AC	2503 ms	35 MB
g++	example_00	AC	5 ms	4 MB
g++	many_query_0_00	AC	1673 ms	53 MB
g++	many_query_0_01	AC	1668 ms	52 MB
g++	many_query_1_00	AC	2097 ms	23 MB
g++	many_query_1_01	AC	2102 ms	23 MB
g++	max_random_00	AC	2175 ms	38 MB
g++	max_random_01	AC	2201 ms	38 MB
g++	max_random_02	AC	2168 ms	38 MB
g++	near_0_and_N_00	AC	2471 ms	26 MB
g++	near_0_and_N_01	AC	2489 ms	26 MB
g++	query_0_then_1_00	AC	2414 ms	38 MB
g++	query_0_then_1_01	AC	2391 ms	38 MB
g++	random_00	AC	1878 ms	32 MB
g++	random_01	AC	1892 ms	32 MB
g++	random_02	AC	1669 ms	31 MB
g++	random_03	AC	99 ms	6 MB
g++	random_04	AC	393 ms	13 MB
g++	small_N_00	AC	87 ms	17 MB
g++	small_N_01	AC	118 ms	17 MB
g++	small_N_02	AC	152 ms	17 MB
g++	small_N_03	AC	178 ms	17 MB
g++	small_N_04	AC	200 ms	17 MB

Back to top page