This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
/*#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")//*/
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "C++/math/psum/psum.hpp"
#include "C++/template.hpp"
int main() {
now(start);
VvyLw::wa_haya_exe();
now(stop);
time(start, stop);
}
// --------------------------------------------------------------------------------------------------------------
inline void VvyLw::solve() noexcept {
int n, q;
std::cin >> n >> q;
man::vec::zhl a(n);
std::cin >> a;
man::psum s(a);
while(q--) {
int l, r;
std::cin >> l >> r;
std::cout << s.sum(l, r) << '\n';
}
}
#line 1 "test/sr_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
/*#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")//*/
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#line 2 "C++/math/psum/psum.hpp"
#include <vector>
#include <numeric>
namespace man {
template <std::integral T> struct psum {
private:
int n;
bool not_built;
std::vector<long long> s;
public:
psum(const std::vector<T> &v): s{0} { std::partial_sum(v.cbegin(), v.cend(), std::back_inserter(s)); }
psum(const int n): n(n), not_built(true), s(n + 1){}
constexpr inline std::vector<long long> get() const noexcept { return s; }
// [l, r]
constexpr inline long long sum(const int l, const int r) const noexcept { return s[r] - s[l]; }
constexpr inline void add(const int l, const int r, const long long x = 1) noexcept {
static_assert(not_built);
s[l] += x;
s[r] -= x;
}
constexpr inline std::vector<long long> build() noexcept {
static_assert(not_built);
std::vector<long long> res;
std::partial_sum(s.cbegin(), s.cend(), std::back_inserter(res));
not_built = false;
res.resize(n);
return res;
}
};
}
/**
* @brief 累積和
*/
#line 2 "C++/template.hpp"
#ifndef TEMPLATE
#define TEMPLATE
#endif
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wsign-compare"
#pragma GCC diagnostic ignored "-Wdeprecated-copy"
#include <bits/stdc++.h>
namespace VvyLw {
enum TestCase { single, multi };
inline void solve() noexcept;
template <TestCase tc = single, int x = 12> constexpr inline void wa_haya_exe() noexcept {
std::cin.tie(nullptr) -> sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(x);
int t = 1;
if constexpr (tc == multi) {
std::cin >> t;
}
for([[maybe_unused]] const auto _: std::views::iota(0, t)) {
solve();
}
}
}
using enum VvyLw::TestCase;
#line 2 "C++/core/alias.hpp"
#ifndef ALIAS
#define ALIAS
#endif
#line 8 "C++/core/alias.hpp"
#include <numbers>
#line 10 "C++/core/alias.hpp"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
namespace internal {
template <typename T> concept num = std::integral<T> || std::floating_point<T>;
}
constexpr int dx[] = {0, 0, 0, -1, 1, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, -1, 1, -1, 1};
constexpr int MOD = 0x3b800001;
constexpr int M0D = 1e9 + 7;
constexpr int INF = 1 << 30;
constexpr long long LINF = (1LL << 61) - 1;
constexpr long double DINF = std::numeric_limits<long double>::infinity();
template <internal::num T> constexpr T LIM = std::numeric_limits<T>::max();
constexpr long double PI = std::numbers::pi;
constexpr long double E = std::numbers::e;
typedef long long i64;
typedef long double ld;
typedef unsigned u32;
typedef unsigned long long u64;
typedef __int128_t i128;
typedef __uint128_t u128;
template <size_t N> using ti = std::array<i64, N>;
typedef ti<3> tri;
template <class T> using pq = std::priority_queue<T>;
template <class T> using pqr = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T> using Tree = __gnu_pbds::tree<T, __gnu_pbds::null_type, std::less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template <class T> using TREE = __gnu_pbds::tree<T, __gnu_pbds::null_type, std::greater<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
/**
* @brief エイリアス
*/
#line 28 "C++/template.hpp"
namespace man {
inline bool isdigit(const std::string &s) noexcept;
std::mt19937 EhaL(std::hash<std::string>()("Huitloxopetl"));
inline std::mt19937 rand() noexcept {
std::random_device seed_gen;
std::mt19937 engine {seed_gen()};
return engine;
}
template <class T, class U> constexpr inline bool chmax(T& a, const U& b) noexcept { if(a < b){ a = b; return true; } return false; }
template <class T, class U> constexpr inline bool chmin(T& a, const U& b) noexcept { if(a > b){ a = b; return true; } return false; }
template <internal::num T, internal::num U> constexpr inline bool overflow_if_add(const T a, const U b) noexcept { return (std::numeric_limits<T>::max() - a) < b; }
template <internal::num T, internal::num U> constexpr inline bool overflow_if_mul(const T a, const U b) noexcept { return (std::numeric_limits<T>::max() / a) < b; }
inline std::string string_replace(const std::string &s, const std::string &a, const std::string &b) noexcept { return std::regex_replace(s, std::regex(a), b); }
inline bool regex_contains(const std::string &s, const std::string &t) noexcept { return std::regex_search(s, std::regex(t)); }
constexpr inline auto yes(const bool ok) noexcept { return ok ? "Yes" : "No"; }
template <internal::num T> constexpr inline T sqr(const T x) noexcept { return x * x; }
template <internal::num T> constexpr inline T cub(const T x) noexcept { return x * x * x; }
template <std::integral T> constexpr inline T mod(T x, const T m) noexcept {
x %= m;
return x < 0 ? x + m : x;
}
template <std::integral T> constexpr inline T pow(T a, T b, const T mod = 0) noexcept {
T ret = 1;
if(mod != 0) {
ret %= mod;
a %= mod;
}
while(b > 0) {
if(b & 1) {
ret *= a;
}
if(mod != 0) {
ret %= mod;
}
a *= a;
if(mod) {
a %= mod;
}
b >>= 1;
}
return ret;
}
constexpr inline long long ceil(const long double x, const long long m) noexcept { return std::ceil(x / m); }
constexpr inline long double round(const long double x, const long long m, const short fx = 0) noexcept {
if(fx == 0) {
return std::round(x / m);
}
const unsigned long long y = pow<unsigned long long>(10, fx);
return std::round((x * y) / m) / y;
}
constexpr inline long double log(const long long x, const long double base = 2) noexcept { return std::log2(x) / std::log2(base); }
template <internal::num T> constexpr inline bool scope(const T a, const T x, const T b) noexcept { return a <= x && x <= b; }
constexpr inline bool isupper(const char c) noexcept { return std::isupper(c); }
inline bool isupper(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= isupper(el);
}
return ok;
}
constexpr inline bool islower(const char c) noexcept { return std::islower(c); }
inline bool islower(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= islower(el);
}
return ok;
}
constexpr inline bool isalpha(const char c) noexcept { return std::isalpha(c); }
inline bool isalpha(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= isalpha(el);
}
return ok;
}
constexpr inline bool isdigit(const char c) noexcept { return std::isdigit(c); }
inline bool isdigit(const std::string &s) noexcept {
bool ok = true, neg = s.front() == '-';
for(const auto &el: s) {
if(neg) {
neg = false;
continue;
}
ok &= isdigit(el);
}
return ok;
}
constexpr inline bool isalnum(const char c) noexcept { return std::isalnum(c); }
inline bool isalnum(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= isalnum(el);
}
return ok;
}
constexpr inline bool isspace(const char c) noexcept { return std::isspace(c); }
inline bool isspace(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= isspace(el);
}
return ok;
}
constexpr inline bool ispunct(const char c) noexcept { return std::ispunct(c); }
inline bool ispunct(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= ispunct(el);
}
return ok;
}
constexpr inline bool isprint(const char c) noexcept { return std::isprint(c); }
inline bool isprint(const std::string &s) noexcept {
bool ok = true;
for(const auto &el: s) {
ok &= isprint(el);
}
return ok;
}
inline auto strins(std::string &s, const int id, const std::string &t) noexcept {
s.insert(id, t);
return std::ssize(s);
}
inline std::string toupper(std::string s) noexcept {
for(auto &c: s) {
c = std::toupper(c);
}
return s;
}
inline std::string tolower(std::string s) noexcept {
for(auto &c: s) {
c = std::tolower(c);
}
return s;
}
inline std::string ten_to(long long n, const int base, const bool upper = true) noexcept {
assert(base <= 10 || base == 16);
if(base == 16) {
std::stringstream ss;
ss << std::hex << n;
const std::string s = ss.str();
return upper ? toupper(s) : s;
}
if(n == 0 || base == 0) {
return "0";
}
std::vector<int> ret;
while(n > 0) {
ret.emplace_back(n % base);
n /= base;
}
std::string s;
for(const auto &e: ret | std::views::reverse) {
s += std::to_string(e);
}
return s;
}
inline long long to_ten(const std::string &s, const int base = 10) noexcept { return std::stoll(s, nullptr, base); }
template <std::integral... Ts> constexpr unsigned long long gcd(const Ts... a) noexcept {
std::vector v = std::initializer_list<std::common_type_t<Ts...>>{a...};
unsigned long long g = 0;
for(const auto &el: v) {
g = std::gcd(g, el);
}
return g;
}
template <std::integral... Ts> constexpr unsigned long long lcm(const Ts... a) noexcept {
std::vector v = std::initializer_list<std::common_type_t<Ts...>>{a...};
unsigned long long l = 1;
for(const auto &el: v) {
l = std::lcm(l, el);
}
return l;
}
template <internal::num... Ts> constexpr auto min(const Ts... a) noexcept { return std::min(std::initializer_list<std::common_type_t<Ts...>>{a...}); }
template <internal::num... Ts> constexpr auto max(const Ts... a) noexcept { return std::max(std::initializer_list<std::common_type_t<Ts...>>{a...}); }
template <class K, class V> inline std::vector<K> key_l(const std::map<K, V> &m, const V val) noexcept {
std::vector<K> keys;
for(auto it = m.cbegin(); it != m.cend(); ++it) {
if(it->second == val) {
keys.emplace_back(it->first);
}
}
return keys;
}
template <class K, class V> constexpr inline K key_min(const std::map<K, V> &m) noexcept { return m.begin()->first; }
template <class K, class V> constexpr inline K key_max(const std::map<K, V> &m) noexcept { return m.rbegin()->first; }
template <class K, class V> constexpr inline V key_min_v(const std::map<K, V> &m) noexcept { return m.begin()->second; }
template <class K, class V> constexpr inline V key_max_v(const std::map<K, V> &m) noexcept { return m.rbegin()->second; }
template <class K, class V> constexpr inline auto val_min(const std::map<K, V> &m) noexcept {
return *std::ranges::min_element(m, [](const std::pair<K, V> &x, const std::pair<K, V> &y) -> bool { return x.second < y.second; });
}
template <class K, class V> constexpr inline auto val_max(const std::map<K, V> &m) noexcept {
return *std::ranges::max_element(m, [](const std::pair<K, V> &x, const std::pair<K, V> &y) -> bool { return x.second < y.second; });
}
template <std::integral T> constexpr inline T count(std::vector<T> v, const T &x) noexcept {
if(!std::ranges::is_sorted(v)) {
std::ranges::sort(v);
}
return std::ranges::upper_bound(v, x) - std::ranges::lower_bound(v, x);
}
template <class T> constexpr inline T inner_prod(const std::vector<T> &v, const std::vector<T> &u, const T init) noexcept { return std::inner_product(v.cbegin(), v.cend(), u.cbegin(), init); }
inline std::vector<int> iota(const int n, const int init = 0) noexcept {
std::vector<int> a(n);
std::iota(a.begin(), a.end(), init);
return a;
}
template <class T> constexpr inline int uniq(T& v) noexcept {
if(!std::ranges::is_sorted(v)) {
std::ranges::sort(v);
}
const auto it = std::ranges::unique(v);
v.erase(it.begin(), it.end());
return std::ssize(v);
}
template <class T> constexpr inline void rotate(T& s, const int idx) noexcept {
const int id = mod<int>(idx, std::ssize(s));
std::ranges::rotate(s, s.begin() + id);
}
template <class T> constexpr inline T set_diff(const T& s, const T& t) noexcept {
assert(std::ranges::is_sorted(s) && std::ranges::is_sorted(t));
T ret;
std::ranges::set_difference(s, t, std::inserter(ret, std::end(ret)));
return ret;
}
template <class T> constexpr inline T set_sum(const T& s, const T& t) noexcept {
assert(std::ranges::is_sorted(s) && std::ranges::is_sorted(t));
T ret;
std::ranges::set_union(s, t, std::inserter(ret, std::end(ret)));
return ret;
}
template <class T> constexpr inline T set_mul(const T& s, const T& t) noexcept {
assert(std::ranges::is_sorted(s) && std::ranges::is_sorted(t));
T ret;
std::ranges::set_intersection(s, t, std::inserter(ret, std::end(ret)));
return ret;
}
template <class T> inline std::vector<T> adj_diff(const std::vector<T> &v) noexcept {
std::vector<T> a;
std::adjacent_difference(v.cbegin(), v.cend(), std::back_inserter(a));
rotate(a, 1);
a.pop_back();
return a;
}
template <class T, class F> inline std::vector<T> isum(const std::vector<T> &v, const F &fn) noexcept {
std::vector<T> s{0};
std::inclusive_scan(v.cbegin(), v.cend(), std::back_inserter(s), fn);
return s;
}
template <class T> inline std::vector<T> rand_extract(const std::vector<T> &v, const int size) noexcept {
std::vector<T> ret;
std::ranges::sample(v, std::back_inserter(ret), size, rand());
return ret;
}
template <class T> inline T rand_extract(const std::vector<T> &v) noexcept {
std::vector<T> ret;
std::ranges::sample(v, std::back_inserter(ret), 1, rand());
return ret.front();
}
template <std::ranges::random_access_range T> inline auto sum(const T &v) noexcept { return std::accumulate(v.cbegin(), v.cend(), decltype(v.front())(0)); }
template <std::ranges::random_access_range T> inline auto sum(const T &v, const int a, const int b) noexcept { return std::accumulate(v.cbegin() + a, v.cbegin() + b, decltype(v.front())(0)); }
template <std::ranges::random_access_range T, class Boolean = bool> inline auto sum(const T &v, const Boolean &fn) noexcept { return std::accumulate(v.cbegin(), v.cend(), decltype(v.front())(0), fn); }
template <std::ranges::random_access_range T, class Boolean = bool> inline auto sum(const T &v, const int a, const int b, const Boolean &fn) noexcept { return std::accumulate(v.cbegin() + a, v.cbegin() + b, decltype(v.front())(0), fn); }
template <internal::num T, class Boolean = bool> constexpr inline T bins(T ok, T ng, const Boolean &fn, const long double eps = 1) noexcept {
while(std::abs(ok - ng) > eps) {
const T mid = (ok + ng) / 2;
(fn(mid) ? ok : ng) = mid;
}
return ok;
}
inline std::vector<std::string> rotate(const std::vector<std::string> &s) noexcept {
const int h = std::ssize(s), w = std::ssize(s.front());
std::vector t(w, std::string(h, {}));
for(const auto i: std::views::iota(0, h)) {
for(const auto j: std::views::iota(0, w)) {
t[j][i] = s[i][j];
}
}
for(const auto i: std::views::iota(0, w)) {
std::ranges::reverse(t[i]);
}
return t;
}
template <internal::num T> inline std::vector<std::vector<T>> rotate(const std::vector<std::vector<T>> &v) noexcept {
const int h = std::ssize(v), w = std::ssize(v.front());
std::vector ret(w, std::vector<T>(h));
for(const auto i: std::views::iota(0, h)) {
for(const auto j: std::views::iota(0, w)) {
ret[j][i] = v[i][j];
}
}
for(const auto i: std::views::iota(0, w)) {
std::ranges::reverse(ret[i]);
}
return ret;
}
template <std::integral T> constexpr inline T factor(T n, const T mod = 0) noexcept {
T ret = 1;
while(n > 0) {
ret *= n--;
if(mod) {
ret %= mod;
}
}
return ret;
}
template <std::integral T> constexpr inline T perm(T n, const T r, const T mod = 0) noexcept {
const T tmp = n;
T ret = 1;
while(n > tmp - r) {
ret *= n--;
if(mod) {
ret %= mod;
}
}
return ret;
}
template <std::integral T> constexpr inline T binom(T n, const T r, const T mod = 0) noexcept {
if(r < 0 || n < r) {
return 0;
}
T ret = 1;
for(const auto i: std::views::iota(1) | std::views::take(r)) {
ret *= n--;
if(mod) {
ret %= mod;
}
ret /= i;
if(mod) {
ret %= mod;
}
}
return ret;
}
constexpr inline bool is_int(const long double n) noexcept { return n == std::floor(n); }
constexpr inline bool is_sqr(const long long n) noexcept { return is_int(std::sqrt(n)); }
}
#line 2 "C++/core/timer.hpp"
#line 5 "C++/core/timer.hpp"
typedef std::chrono::system_clock::time_point Timer;
Timer start, stop;
#if local
inline void now(Timer &t) noexcept { t = std::chrono::system_clock::now(); }
inline void time(const Timer &t1, const Timer &t2) noexcept { std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count() << "ms\n"; }
#else
void now(Timer &t){ void(0); }
void time(const Timer &t1, const Timer &t2){ void(0); }
#endif
/**
* @brief タイマー
*/
#line 2 "C++/core/myvector.hpp"
#line 4 "C++/core/myvector.hpp"
#ifndef ALIAS
namespace internal {
template <typename T> concept num = std::integral<T> || std::floating_point<T>;
}
#endif
namespace man {
namespace vec {
template <class T> using V = std::vector<T>;
typedef V<long long> zhl;
typedef V<unsigned long long> uzhl;
typedef V<long double> dec;
typedef V<char> chr;
typedef V<std::string> str;
typedef V<bool> bol;
typedef V<zhl> zhl2;
typedef V<uzhl> uzhl2;
typedef V<dec> dec2;
typedef V<chr> chr2;
typedef V<str> str2;
typedef V<bol> bol2;
#ifdef EDGE
typedef V<man::edge> edg;
typedef V<edg> edg2;
#endif
template <class T, class U> inline V<U> ndiv(T&& n, U&& v) noexcept {
return V<U>(std::forward<T>(n), std::forward<U>(v));
}
template <class T, class... Ts> inline decltype(auto) ndiv(T&& n, Ts&&... v) noexcept {
return V<decltype(ndiv(std::forward<Ts>(v)...))>(std::forward<T>(n), ndiv(std::forward<Ts>(v)...));
}
template <internal::num T> constexpr V<T>& operator++(V<T>& v) noexcept { for(auto &el: v){ el++; } return v; }
template <internal::num T> constexpr V<T>& operator--(V<T>& v) noexcept { for(auto &el: v){ el--; } return v; }
template <internal::num T, internal::num U> constexpr V<T>& operator+=(V<T>& v, const U x) noexcept { for(auto &el: v){ el += x; } return v; }
template <internal::num T, internal::num U> constexpr V<T>& operator-=(V<T>& v, const U x) noexcept { for(auto &el: v){ el -= x; } return v; }
template <internal::num T, internal::num U> constexpr V<T>& operator*=(V<T>& v, const U x) noexcept { for(auto &el: v){ el *= x; } return v; }
template <internal::num T, internal::num U> constexpr V<T>& operator/=(V<T>& v, const U x) noexcept { for(auto &el: v){ el /= x; } return v; }
template <std::integral T, std::integral U> constexpr V<T>& operator%=(V<T>& v, const U x) noexcept { for(auto &el: v){ el %= x; } return v; }
template <internal::num T, internal::num U> constexpr V<T> operator+(const V<T>& v, const U x) noexcept { V<T> ret = v; ret += x; return ret; }
template <internal::num T, internal::num U> constexpr V<T> operator-(const V<T>& v, const U x) noexcept { V<T> ret = v; ret -= x; return ret; }
template <internal::num T, internal::num U> constexpr V<T> operator*(const V<T>& v, const U x) noexcept { V<T> ret = v; ret *= x; return ret; }
template <internal::num T, internal::num U> constexpr V<T> operator/(const V<T>& v, const U x) noexcept { V<T> ret = v; ret /= x; return ret; }
template <std::integral T, std::integral U> constexpr V<T> operator%(const V<T>& v, const U x) noexcept { V<T> ret = v; ret %= x; return ret; }
}
}
#line 2 "C++/core/mypair.hpp"
#line 8 "C++/core/mypair.hpp"
#ifndef ALIAS
namespace internal {
template <typename T> concept num = std::integral<T> || std::floating_point<T>;
}
#endif
namespace man {
namespace pav {
template <class T, class U> using P = std::pair<T, U>;
template <class T> using PP = P<T, T>;
typedef PP<long long> zhl;
typedef PP<long double> dec;
typedef PP<char> chr;
typedef PP<std::string> str;
template <internal::num T> constexpr PP<T> operator+(const PP<T>& a, const PP<T>& b) noexcept { return {a.first + b.first, a.second + b.second}; }
template <internal::num T> constexpr PP<T> operator-(const PP<T>& a, const PP<T>& b) noexcept { return {a.first - b.first, a.second - b.second}; }
template <internal::num T> constexpr PP<T> operator-(const PP<T>& a) noexcept { return {-a.first, -a.second}; }
template <internal::num T, class U> constexpr PP<T> operator*(const PP<T>& a, const U& b) noexcept { return {a.first * b, a.second * b}; }
template <internal::num T, class U> constexpr PP<T> operator/(const PP<T>& a, const U& b) noexcept { return {a.first / b, a.second / b}; }
template <internal::num T> constexpr PP<T>& operator+=(PP<T>& a, const PP<T>& b) noexcept { return a = a + b; }
template <internal::num T> constexpr PP<T>& operator-=(PP<T>& a, const PP<T>& b) noexcept { return a = a - b; }
template <internal::num T, internal::num U> constexpr PP<T>& operator*=(PP<T>& a, const U& b) noexcept { return a = a * b; }
template <internal::num T, internal::num U> PP<T>& operator/=(PP<T>& a, const U& b) noexcept { return a = a / b; }
template <class T> constexpr bool operator==(const PP<T> &p, const PP<T> &q) noexcept { return p.first == q.first && p.second == q.second; }
template <class T> constexpr bool operator!=(const PP<T> &p, const PP<T> &q) noexcept { return !(p == q); }
template <class T> constexpr bool operator<(const PP<T> &p, const PP<T> &q) noexcept { if(p.first == q.first){ return p.second < q.second; } return p.first < q.first; }
template <class T> constexpr bool operator<=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first == q.first){ return p.second <= q.second; } return p.first < q.first; }
template <class T> constexpr bool operator>(const PP<T> &p, const PP<T> &q) noexcept { if(p.first == q.first){ return p.second > q.second; } return p.first > q.first; }
template <class T> constexpr bool operator>=(const PP<T> &p, const PP<T> &q) noexcept { if(p.first == q.first){ return p.second >= q.second; } return p.first > q.first; }
template <class T, class U> constexpr bool operator==(const P<T, U> &p, const P<T, U> &q) noexcept { return p.first == q.first && p.second == q.second; }
template <class T, class U> constexpr bool operator!=(const P<T, U> &p, const P<T, U> &q) noexcept { return !(p == q); }
template <class T, class U> constexpr bool operator<(const P<T, U> &p, const P<T, U> &q) noexcept { if(p.first == q.first){ return p.second < q.second; } return p.first < q.first; }
template <class T, class U> constexpr bool operator<=(const P<T, U> &p, const P<T, U> &q) noexcept { if(p.first == q.first){ return p.second <= q.second; } return p.first < q.first; }
template <class T, class U> constexpr bool operator>(const P<T, U> &p, const P<T, U> &q) noexcept { if(p.first == q.first){ return p.second > q.second; } return p.first > q.first; }
template <class T, class U> constexpr bool operator>=(const P<T, U> &p, const P<T, U> &q) noexcept { if(p.first == q.first){ return p.second >= q.second; } return p.first > q.first; }
template <internal::num T> constexpr inline PP<T> rotate(const PP<T>& a) noexcept { return {-a.second, a.first}; } // 90 degree ccw
template <internal::num T> constexpr inline dec rotate(const PP<T>& a, const int ang) noexcept {
assert(0 <= ang && ang < 360);
const long double rad = PI * ang / 180;
return {a.first * std::cos(rad) - a.second * std::sin(rad), a.first * std::sin(rad) + a.second * std::cos(rad)};
}
template <internal::num T> constexpr inline T dot(const PP<T>& a, const PP<T>& b) noexcept { return a.first * b.first + a.second * b.second; }
template <internal::num T> constexpr inline T cross(const PP<T>& a, const PP<T>& b) noexcept { return dot(rotate(a), b); }
template <internal::num T> constexpr inline T square(const PP<T>& a) noexcept { return dot(a, a); }
template <internal::num T> constexpr inline long double grad(const PP<T>& a) noexcept { assert(a.first != 0); return 1.0L * a.second / a.first; }
template <internal::num T> constexpr inline long double abs(const PP<T>& a) noexcept { return std::hypotl(a.first, a.second); }
template <std::integral T> constexpr inline T lcm(const PP<T>& a) noexcept { return std::lcm(a.first, a.second); }
template <std::integral T> constexpr inline T gcd(const PP<T>& a) noexcept { return std::gcd(a.first, a.second); }
template <std::integral T> constexpr inline PP<T> extgcd(const PP<T> &p) noexcept {
T x = 1, y = 0, t1 = 0, t2 = 0, t3 = 1, a, b;
std::tie(a,b) = p;
while(b > 0) {
t1 = a / b, a -= t1 * b;
std::swap(a, b);
x -= t1 * t2;
std::swap(x, t2);
y -= t1 * t3;
std::swap(y, t3);
}
return {x, y};
}
template <std::integral T> constexpr inline PP<T> normalize(PP<T> a) noexcept {
if(a == PP<T>{}) {
return a;
}
a /= gcd(a);
if(a < PP<T>{}) {
a = -a;
}
return a;
}
template <class T, class U> constexpr inline P<U, T> swap(const P<T, U> &p) noexcept { const P<U, T> ret = {p.second, p.first}; return ret; }
template <class T, class U> inline std::vector<P<U, T>> swap(const std::vector<P<T, U>> &vp) noexcept {
std::vector<P<U, T>> ret;
for(const auto &el: vp) {
ret.emplace_back(swap(el));
}
return ret;
}
template <class T, class U> inline std::vector<T> first(const std::vector<P<T, U>> &vp) noexcept {
std::vector<T> ret;
for(const auto &el: vp) {
ret.emplace_back(el.first);
}
return ret;
}
template <class T, class U> inline std::vector<U> second(const std::vector<P<T, U>> &vp) noexcept {
std::vector<U> ret;
for(const auto &el: vp) {
ret.emplace_back(el.second);
}
return ret;
}
}
}
#line 2 "C++/core/io/input.hpp"
#line 8 "C++/core/io/input.hpp"
#ifndef TEMPLATE
namespace man {
constexpr inline bool isdigit(const char c) noexcept { return std::isdigit(c); }
inline bool isdigit(const std::string &s) noexcept {
bool ok = true, neg = s.front() == '-';
for(const auto &el: s) {
if(neg) {
neg = false;
continue;
}
ok &= isdigit(el);
}
return ok;
}
}
#endif
namespace IO {
inline std::istream& operator>>(std::istream &is, __int128_t &val) noexcept {
std::string s;
std::cin >> s;
assert(man::isdigit(s));
bool neg = s.front() == '-';
val = 0;
for(const auto &el: s) {
if(neg) {
neg = false;
continue;
}
val = 10 * val + el - '0';
}
if(s.front()=='-') {
val = -val;
}
return is;
}
template <class T, class U> inline std::istream& operator>>(std::istream &is, std::pair<T, U> &p) noexcept { is >> p.first >> p.second; return is; }
template <std::ranges::random_access_range T> requires (!std::same_as<std::remove_cvref_t<T>, std::string> && !std::same_as<std::remove_cvref_t<T>, std::string_view> && !std::is_array_v<std::remove_cvref_t<T>>) inline std::istream& operator>>(std::istream &is, T &v) noexcept { for(auto &el: v){ is >> el; } return is; }
template <class Head, class... Tail> inline bool input(Head &head, Tail &...tail) noexcept {
if(!(std::cin >> head)) {
return false;
}
if constexpr(sizeof...(Tail) > 0) {
input(tail...);
}
return true;
}
} // IO
/**
* @brief 入力
*/
#line 2 "C++/core/io/output.hpp"
#line 6 "C++/core/io/output.hpp"
namespace IO {
inline std::ostream &operator<<(std::ostream &dest, const __int128_t &value) noexcept {
std::ostream::sentry s(dest);
constexpr char dig[] = "0123456789";
if(s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = std::end(buffer);
do {
--d;
*d = dig[tmp % 10];
tmp /= 10;
} while(tmp != 0);
if(value < 0) {
--d;
*d = '-';
}
const int len = std::end(buffer) - d;
if(dest.rdbuf() -> sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
template <class T, class U> inline std::ostream& operator<<(std::ostream &os, const std::pair<T, U> &p) noexcept { os << p.first << ' ' << p.second; return os; }
template <class K, class V> inline std::ostream& operator<<(std::ostream &os, const std::map<K, V> &m) noexcept {
if(!m.empty()) {
os << m.begin()->first << ' ' << m.begin()->second;
for(auto i = m.begin(); ++i != m.end();) {
os << '\n' << i->first << ' ' << i->second;
}
}
return os;
}
template <std::ranges::range T> requires (!std::same_as<std::remove_cvref_t<T>, std::string> && !std::same_as<std::remove_cvref_t<T>, std::string_view> && !std::is_array_v<std::remove_cvref_t<T>>) inline std::ostream& operator<<(std::ostream &os, const T &v) noexcept {
if(!v.empty()) {
os << *v.cbegin();
for(auto i = v.cbegin(); ++i != v.cend();) {
os << ' ' << *i;
}
}
return os;
}
enum Flash { non_flush, flush };
template <Flash f = non_flush, class Head, class... Tail> inline void print(const Head& head, const Tail& ...tail) noexcept {
std::cout << head;
if constexpr(sizeof...(Tail) > 0) {
std::cout << ' ';
print<f>(tail...);
} else {
if constexpr(f == flush) {
std::cout.flush();
}
}
}
inline void println() noexcept { std::cout << '\n'; }
template <Flash f = non_flush, class Head, class... Tail> inline void println(const Head& head, const Tail& ...tail) noexcept { print<f>(head, tail...); std::cout << '\n'; }
} // IO
using enum IO::Flash;
#if local
//https://gist.github.com/naskya/1e5e5cd269cfe16a76988378a60e2ca3
#include <C++/core/io/debug_print.hpp>
#else
#define dump(...) static_cast<void>(0)
#endif
/**
* @brief 出力
*/
#line 377 "C++/template.hpp"
#define REP(n) for([[maybe_unused]] const auto _: std::views::iota(0, (n)))
using namespace IO;
using namespace std::views;
namespace iter = std::ranges;
/**
* @brief テンプレート
* @docs docs/template.md
*/
#line 7 "test/sr_sum.test.cpp"
int main() {
now(start);
VvyLw::wa_haya_exe();
now(stop);
time(start, stop);
}
// --------------------------------------------------------------------------------------------------------------
inline void VvyLw::solve() noexcept {
int n, q;
std::cin >> n >> q;
man::vec::zhl a(n);
std::cin >> a;
man::psum s(a);
while(q--) {
int l, r;
std::cin >> l >> r;
std::cout << s.sum(l, r) << '\n';
}
}