shogo-library
競技プログラミング用の C++ ライブラリ
test/yosupo/static-range-sum.test.cpp
- View this file on GitHub
- Last update: 2026-10-13 06:02:01+09:00
- Problem: https://judge.yosupo.jp/problem/static_range_sum
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <iostream>
#include <vector>
#include "../../src/base/vector_func.hpp"
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<long long> a(n);
for (auto& x : a) std::cin >> x;
// s[i] = a[0] + ... + a[i-1]
std::vector<long long> s = cumulative_sum(a);
while (q--) {
int l, r;
std::cin >> l >> r;
std::cout << s[r] - s[l] << '\n';
}
}#line 1 "test/yosupo/static-range-sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <iostream>
#include <vector>
#line 2 "src/base/vector_func.hpp"
/**
* @file vector_func.hpp
* @brief vector に対する演算子と関数
*/
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <numeric>
#line 14 "src/base/vector_func.hpp"
#line 2 "src/base/traits.hpp"
/**
* @file traits.hpp
* @brief 型特性
*/
#line 9 "src/base/traits.hpp"
#include <iterator>
#include <set>
#include <type_traits>
#include <utility>
namespace detail {
using std::begin, std::end;
template <class T, class = void>
struct is_range_impl : std::false_type {};
template <class T>
struct is_range_impl<T, std::void_t<decltype(begin(std::declval<T&>()), end(std::declval<T&>()))>> : std::true_type {};
} // namespace detail
template <class T>
struct is_range : detail::is_range_impl<T>::type {};
template <class T>
inline constexpr bool is_range_v = is_range<T>::value;
#define HAS_METHOD(func_name) \
namespace detail { \
template <class T, class = void> \
struct has_##func_name##_impl : std::false_type {}; \
template <class T> \
struct has_##func_name##_impl<T, std::void_t<decltype(std::declval<T>().func_name())>> \
: std::true_type {}; \
} \
template <class T> \
struct has_##func_name : detail::has_##func_name##_impl<T>::type {}; \
template <class T> \
inline constexpr bool has_##func_name##_v = has_##func_name<T>::value;
#define HAS_METHOD_ARG(func_name) \
namespace detail { \
template <class T, typename U, class = void> \
struct has_##func_name##_impl : std::false_type {}; \
template <class T, typename U> \
struct has_##func_name##_impl<T, U, std::void_t<decltype(std::declval<T>().func_name(std::declval<U>()))>> \
: std::true_type {}; \
} \
template <class T, typename U> \
struct has_##func_name : detail::has_##func_name##_impl<T, U>::type {}; \
template <class T, typename U> \
inline constexpr bool has_##func_name##_v = has_##func_name<T, U>::value;
HAS_METHOD(repr)
HAS_METHOD(type_str)
HAS_METHOD(initializer_str)
HAS_METHOD(max)
HAS_METHOD(min)
HAS_METHOD(reversed)
HAS_METHOD(sorted)
HAS_METHOD(sum)
HAS_METHOD(product)
HAS_METHOD(product_xor)
HAS_METHOD_ARG(count)
HAS_METHOD_ARG(find)
HAS_METHOD_ARG(lower_bound)
HAS_METHOD_ARG(upper_bound)
#define ENABLE_IF_T_IMPL(expr) std::enable_if_t<expr, std::nullptr_t> = nullptr
#define ENABLE_IF_T(...) ENABLE_IF_T_IMPL((__VA_ARGS__))
template <class C>
using mem_value_type = typename C::value_type;
template <class C>
using mem_difference_type = typename C::difference_type;
namespace detail {
template <class T, class = void>
struct is_sorted_container_impl : std::false_type {};
template <class T>
struct is_sorted_container_impl<std::set<T>> : std::true_type {};
template <class T>
struct is_sorted_container_impl<std::multiset<T>> : std::true_type {};
} // namespace detail
template <class T>
struct is_sorted_container : detail::is_sorted_container_impl<T>::type {};
template <class T>
inline constexpr bool is_sorted_container_v = is_sorted_container<T>::value;
#line 16 "src/base/vector_func.hpp"
template <typename T>
std::vector<std::ptrdiff_t> sorted_idx(const std::vector<T> &v, bool reverse = false) {
std::vector<std::ptrdiff_t> ret(v.size());
std::iota(ret.begin(), ret.end(), 0);
std::sort(ret.begin(), ret.end(), [&](std::ptrdiff_t i, std::ptrdiff_t j) {
return v[i] < v[j];
});
if (reverse) std::reverse(ret.begin(), ret.end());
return ret;
}
template <typename T>
inline std::vector<T> &operator++(std::vector<T> &v) {
for (auto &e : v) e++;
return v;
}
template <typename T>
inline std::vector<T> operator++(std::vector<T> &v, int) {
auto res = v;
for (auto &e : v) e++;
return res;
}
template <typename T>
inline std::vector<T> &operator--(std::vector<T> &v) {
for (auto &e : v) e--;
return v;
}
template <typename T>
inline std::vector<T> operator--(std::vector<T> &v, int) {
auto res = v;
for (auto &e : v) e--;
return res;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> &operator+=(std::vector<T> &v1, const std::vector<U> &v2) {
if (v2.size() > v1.size()) {
v1.resize(v2.size());
}
for (size_t i = 0; i < v2.size(); i++) {
v1[i] += v2[i];
}
return v1;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> operator+(const std::vector<T> &v1, const std::vector<U> &v2) {
std::vector<T> res(v1);
return res += v2;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> &operator+=(std::vector<T> &v, const U &u) {
for (T &e : v) {
e += u;
}
return v;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> operator+(const std::vector<T> &v, const U &u) {
std::vector<T> res(v);
return res += u;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> operator+(const U &u, const std::vector<T> &v) {
std::vector<T> res(v);
return res += u;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> &operator*=(std::vector<T> &v1, const std::vector<U> &v2) {
if (v2.size() > v1.size()) {
v1.resize(v2.size());
}
for (size_t i = 0; i < v2.size(); i++) {
v1[i] *= v2[i];
}
for (size_t i = v2.size(); i < v1.size(); i++) {
v1[i] *= U(0);
}
return v1;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> operator*(const std::vector<T> &v1, const std::vector<U> &v2) {
std::vector<T> res(v1);
return res *= v2;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> &operator*=(std::vector<T> &v, const U &u) {
for (T &e : v) {
e *= u;
}
return v;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> operator*(const std::vector<T> &v, const U &u) {
std::vector<T> res(v);
return res *= u;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> operator*(const U &u, const std::vector<T> &v) {
std::vector<T> res(v);
return res *= u;
}
template <typename T, typename U>
inline std::vector<T> &assign(std::vector<T> &v1, const std::vector<U> &v2) {
v1.assign(v2.begin(), v2.end());
return v1;
}
template <typename T, typename U>
inline std::vector<T> &extend(std::vector<T> &v1, const std::vector<U> &v2) {
v1.insert(v1.end(), v2.begin(), v2.end());
return v1;
}
template <typename T, typename U, ENABLE_IF_T(std::is_convertible_v<U, T>)>
inline std::vector<T> &operator|=(std::vector<T> &v1, const std::vector<U> &v2) {
return extend(v1, v2);
}
template <typename T, typename U, ENABLE_IF_T(std::is_integral_v<U>)>
inline std::vector<T> &operator|=(std::vector<T> &v, const U &u) {
std::vector<T> w(v);
v.clear();
for (int i = 0; i < u; i++) {
extend(v, w);
}
return v;
}
template <typename T, typename U, ENABLE_IF_T(std::is_integral_v<U>)>
inline std::vector<T> operator|(const std::vector<T> &v, const U &u) {
std::vector<T> res(v);
return res |= u;
}
template <typename T, typename U, ENABLE_IF_T(std::is_integral_v<U>)>
inline std::vector<T> operator|(const U &u, const std::vector<T> &v) {
std::vector<T> res(v);
return res |= u;
}
template <typename T>
inline std::vector<T> abs(const std::vector<T> &v) {
std::vector<T> ret;
ret.reserve(v.size());
for (const T &e : v) ret.push_back(std::abs(e));
return ret;
}
template <typename T>
std::vector<T> cumulative_sum(std::vector<T> v) {
v.insert(v.begin(), T{});
std::vector<T> ret(v.size());
std::partial_sum(v.begin(), v.end(), ret.begin());
return ret;
}
template <typename T, ENABLE_IF_T(std::is_integral_v<T>)>
std::vector<T> iota(T n) {
assert(n >= 0);
std::vector<T> ret(n);
std::iota(ret.begin(), ret.end(), 0);
return ret;
}
template <typename T>
std::vector<T> unique(const std::vector<T> &v) {
std::vector<T> res(v);
std::sort(res.begin(), res.end());
res.erase(std::unique(res.begin(), res.end()), res.end());
return res;
}
inline long long radix_convert(const std::vector<long long> &v, int base = 10) {
long long res = 0;
for (long long d : v) {
res = res * base + d;
}
return res;
}
inline std::vector<long long> radix_convert(long long v, int base = 10) {
std::vector<long long> res;
while (v > 0) {
res.push_back(v % base);
v /= base;
}
std::reverse(res.begin(), res.end());
return res;
}
#line 7 "test/yosupo/static-range-sum.test.cpp"
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<long long> a(n);
for (auto& x : a) std::cin >> x;
// s[i] = a[0] + ... + a[i-1]
std::vector<long long> s = cumulative_sum(a);
while (q--) {
int l, r;
std::cin >> l >> r;
std::cout << s[r] - s[l] << '\n';
}
}