#define PROBLEM "https://yukicoder.me/problems/no/631"
#include <functional>
#include <iostream>
#include <vector>
#include "Mylib/DataStructure/SegmentTree/starry_sky_tree.cpp"
#include "Mylib/IO/input_tuples.cpp"
#include "Mylib/IO/input_vector.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N;
std::cin >> N;
auto seg = hl::starry_sky_tree<int64_t, std::greater<>>(N - 1);
auto T = hl::input_vector<int64_t>(N - 1);
for (int i = 0; i < N - 1; ++i) {
T[i] += 3 * (N - 1 - i);
}
seg.init_with_vector(T);
int M;
std::cin >> M;
for (auto [L, R, D] : hl::input_tuples<int, int, int>(M)) {
--L, --R;
seg.update(L, R + 1, D);
auto ans = seg.fold_all();
std::cout << ans << std::endl;
}
return 0;
}
#line 1 "test/yukicoder/631/main.starry_sky.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/631"
#include <functional>
#include <iostream>
#include <vector>
#line 2 "Mylib/DataStructure/SegmentTree/starry_sky_tree.cpp"
#include <algorithm>
#include <cassert>
#include <optional>
#line 6 "Mylib/DataStructure/SegmentTree/starry_sky_tree.cpp"
namespace haar_lib {
template <typename T, typename Compare>
class starry_sky_tree {
public:
using value_type = T;
private:
int depth_, size_, hsize_;
std::vector<T> data_;
Compare compare_ = Compare();
T f(T a, T b) const {
return compare_(a, b) ? a : b;
}
void bottom_up(int i) {
if (i > size_) return;
while (i >= 1) {
if (i < hsize_) {
const auto d = f(data_[i << 1 | 0], data_[i << 1 | 1]);
data_[i << 1 | 0] -= d;
data_[i << 1 | 1] -= d;
data_[i] += d;
}
i >>= 1;
}
}
std::optional<T> get(int i, int l, int r, int s, int t, T val) const {
if (r <= s or t <= l) return std::nullopt;
if (s <= l and r <= t) return val + data_[i];
auto a = get(i << 1 | 0, l, (l + r) / 2, s, t, val + data_[i]);
auto b = get(i << 1 | 1, (l + r) / 2, r, s, t, val + data_[i]);
if (not a) return b;
if (not b) return a;
return f(*a, *b);
}
public:
starry_sky_tree() {}
starry_sky_tree(int n) : depth_(n > 1 ? 32 - __builtin_clz(n - 1) + 1 : 1),
size_(1 << depth_),
hsize_(size_ / 2),
data_(size_, 0) {}
void update(int l, int r, T val) {
assert(0 <= l and l <= r and r <= hsize_);
int L = l + hsize_;
int R = r + hsize_;
while (L < R) {
if (R & 1) --R, data_[R] += val;
if (L & 1) data_[L] += val, ++L;
L >>= 1;
R >>= 1;
}
bottom_up(l + hsize_);
bottom_up(r + hsize_);
}
T fold(int l, int r) const {
assert(0 <= l and l <= r and r <= hsize_);
return *get(1, 0, hsize_, l, r, 0);
}
T fold_all() const {
return data_[1];
}
template <typename U>
void init_with_vector(std::vector<U> &a) {
for (int i = 0; i < (int) a.size(); ++i) {
data_[hsize_ + i] = a[i];
}
for (int i = hsize_; --i >= 1;) {
data_[i] = f(data_[i << 1 | 0], data_[i << 1 | 1]);
}
for (int i = size_; --i > 1;) {
data_[i] -= data_[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>
#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 4 "Mylib/IO/input_vector.cpp"
namespace haar_lib {
template <typename T>
std::vector<T> input_vector(int N) {
std::vector<T> ret(N);
for (int i = 0; i < N; ++i) std::cin >> ret[i];
return ret;
}
template <typename T>
std::vector<std::vector<T>> input_vector(int N, int M) {
std::vector<std::vector<T>> ret(N);
for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
return ret;
}
} // namespace haar_lib
#line 9 "test/yukicoder/631/main.starry_sky.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N;
std::cin >> N;
auto seg = hl::starry_sky_tree<int64_t, std::greater<>>(N - 1);
auto T = hl::input_vector<int64_t>(N - 1);
for (int i = 0; i < N - 1; ++i) {
T[i] += 3 * (N - 1 - i);
}
seg.init_with_vector(T);
int M;
std::cin >> M;
for (auto [L, R, D] : hl::input_tuples<int, int, int>(M)) {
--L, --R;
seg.update(L, R + 1, D);
auto ans = seg.fold_all();
std::cout << ans << std::endl;
}
return 0;
}
test/yukicoder/631/main.starry_sky.test.cpp
Input tuple
(Mylib/IO/input_tuple.cpp)