#line 1 "test/yukicoder/789/main.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/789"
#include <iostream>
#line 2 "Mylib/AlgebraicStructure/Monoid/sum.cpp"
namespace haar_lib {
template <typename T>
struct sum_monoid {
using value_type = T;
value_type operator()() const { return 0; }
value_type operator()(value_type a, value_type b) const { return a + b; }
};
} // namespace haar_lib
#line 2 "Mylib/DataStructure/SegmentTree/dynamic_segment_tree.cpp"
#include <cstdint>
namespace haar_lib {
template <typename Monoid>
class dynamic_segment_tree {
public:
using value_type = typename Monoid::value_type;
private:
struct node {
value_type val;
node *left = nullptr, *right = nullptr;
node(const value_type &val) : val(val) {}
};
Monoid M_;
int64_t depth_, size_, hsize_;
node *root_ = nullptr;
value_type eval(node *t) const {
return t ? t->val : M_();
}
node *update(node *t, int64_t l, int64_t r, int64_t pos, const value_type &val) {
if (r - l == 1) {
if (t)
t->val = val;
else
t = new node(val);
} else {
const int64_t m = (l + r) / 2;
if (not t) t = new node(val);
if (pos < m)
t->left = update(t->left, l, m, pos, val);
else
t->right = update(t->right, m, r, pos, val);
t->val = M_(eval(t->left), eval(t->right));
}
return t;
}
value_type get(node *t, int64_t l, int64_t r, int64_t x, int64_t y) const {
if (not t) return M_();
if (x <= l and r <= y) return t ? t->val : M_();
if (r < x or y < l) return M_();
int64_t m = (l + r) >> 1;
return M_(get(t->left, l, m, x, y), get(t->right, m, r, x, y));
}
public:
dynamic_segment_tree() {}
dynamic_segment_tree(int64_t n) : depth_(n > 1 ? 64 - __builtin_clzll(n - 1) + 1 : 1),
size_(1LL << depth_),
hsize_(size_ / 2) {
root_ = new node(M_());
}
void set(int64_t i, const value_type &x) {
update(root_, 0, hsize_, i, x);
}
void update(int64_t i, const value_type &x) {
set(i, M_((*this)[i], x));
}
value_type fold(int64_t l, int64_t r) const {
return get(root_, 0, hsize_, l, r);
}
value_type operator[](int64_t i) const {
return fold(i, i + 1);
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples.cpp"
#include <tuple>
#include <utility>
#include <vector>
#line 6 "Mylib/IO/input_tuple.cpp"
namespace haar_lib {
template <typename T, size_t... I>
static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
}
template <typename T, typename U>
std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
s >> value.first >> value.second;
return s;
}
template <typename... Args>
std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
return s;
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuples {
struct iter {
using value_type = std::tuple<Args...>;
value_type value;
bool fetched = false;
int N, c = 0;
value_type operator*() {
if (not fetched) {
std::cin >> value;
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuples(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples(int N) {
return InputTuples<Args...>(N);
}
} // namespace haar_lib
#line 7 "test/yukicoder/789/main.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int n;
std::cin >> n;
hl::dynamic_segment_tree<hl::sum_monoid<int64_t>> seg(1000000001);
int64_t ans = 0;
for (auto [q, x, y] : hl::input_tuples<int, int, int>(n)) {
if (q == 0) {
seg.update(x, y);
} else {
ans += seg.fold(x, y + 1);
}
}
std::cout << ans << "\n";
return 0;
}
test/yukicoder/789/main.test.cpp
Sum monoid
(Mylib/AlgebraicStructure/Monoid/sum.cpp)