-
Notifications
You must be signed in to change notification settings - Fork 25
/
dynamic_sequence_range_affine_range_sum.test.cpp
66 lines (61 loc) · 1.86 KB
/
dynamic_sequence_range_affine_range_sum.test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// @brief Dynamic Range Affine Range Sum
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum"
#include "cp-algo/math/modint.hpp"
#include "cp-algo/data_structures/treap/metas/reverse.hpp"
#include "cp-algo/data_structures/treap.hpp"
#include <bits/stdc++.h>
using namespace std;
using namespace cp_algo::data_structures::treap;
using base = cp_algo::math::modint<998244353>;
using meta = metas::reverse_meta<base>;
using node_t = node<meta>;
using treap = node_t::treap;
void solve() {
istream_iterator<int> input(cin);
int n = *input++;
int q = *input++;
vector<treap> nodes(n);
generate_n(begin(nodes), n, [&](){
return node_t::make_treap(meta(*input++));
});
auto me = node_t::build(nodes);
while(q--) {
int t = *input++;
if(t == 0) {
int i = *input++;
base x = *input++;
node_t::insert(me, i, node_t::make_treap(meta(x)));
} else if(t == 1) {
node_t::erase(me, *input++);
} else if(t == 2) {
int l = *input++;
int r = *input++;
node_t::exec_on_segment(me, l, r, [](auto &t) {
_safe_meta(t, reverse = 1);
});
} else if(t == 3) {
int l = *input++;
int r = *input++;
base b = *input++;
base c = *input++;
node_t::exec_on_segment(me, l, r, [b, c](auto &t) {
_safe_meta(t, add_push(meta::lin(b, c)));
});
} else {
int l = *input++;
int r = *input++;
node_t::exec_on_segment(me, l, r, [](auto t) {
cout << _safe_meta(t, sum) << "\n";
});
}
}
}
signed main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
while(t--) {
solve();
}
}