test/yosupo-judge/static_range_sum/main.test.cpp
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <iostream>
#include "Mylib/Algorithm/cumulative_sum_1d.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, Q;
std::cin >> N >> Q;
auto a = hl::input_vector<int64_t>(N);
auto c = hl::cumulative_sum_1d_builder<int64_t>(N).update(a).build();
for (auto [l, r] : hl::input_tuples<int, int>(Q)) {
std::cout << c.fold(l, r) << "\n";
}
return 0;
}
#line 1 "test/yosupo-judge/static_range_sum/main.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <iostream>
#line 2 "Mylib/Algorithm/cumulative_sum_1d.cpp"
#include <cassert>
#include <functional>
#include <vector>
namespace haar_lib {
template <typename T>
class cumulative_sum_1d {
public:
using value_type = T;
private:
template <typename>
friend class cumulative_sum_1d_builder;
int N_;
std::vector<T> data_;
public:
T fold(int l, int r) const {
assert(0 <= l and l <= r and r <= N_);
return data_[r] - data_[l];
}
};
template <typename T>
class cumulative_sum_1d_builder {
int N_;
std::vector<T> data_;
public:
cumulative_sum_1d_builder() {}
cumulative_sum_1d_builder(int N) : N_(N), data_(N + 1) {}
auto& update(const std::vector<T>& a) {
for (int i = 0; i < N_; ++i) data_[i + 1] += a[i];
return *this;
}
auto& update(int i, const T& val) {
assert(0 <= i and i < N_);
data_[i + 1] += val;
return *this;
}
auto build() const {
cumulative_sum_1d<T> ret;
ret.data_ = data_;
ret.N_ = N_;
for (int i = 0; i < N_; ++i) ret.data_[i + 1] += ret.data_[i];
return ret;
}
};
} // 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 7 "test/yosupo-judge/static_range_sum/main.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, Q;
std::cin >> N >> Q;
auto a = hl::input_vector<int64_t>(N);
auto c = hl::cumulative_sum_1d_builder<int64_t>(N).update(a).build();
for (auto [l, r] : hl::input_tuples<int, int>(Q)) {
std::cout << c.fold(l, r) << "\n";
}
return 0;
}
Back to top page