test/library_checker/data_structure/static_range_sum_2.test.cpp

View this file on GitHub
Last update: 2022-07-19 22:43:05+09:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

可逆累積和 (data_structure/sequence/invertible_cumulative_sum.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <bits/stdc++.h>
using namespace std;
#include "../../../data_structure/sequence/invertible_cumulative_sum.hpp"
int main(){
  int N, Q;
  cin >> N >> Q;
  vector<long long> a(N);
  for (int i = 0; i < N; i++){
    cin >> a[i];
  }
  invertible_cumulative_sum<long long> S(a, plus<long long>(), negate<long long>(), 0);
  for (int i = 0; i < Q; i++){
    int l, r;
    cin >> l >> r;
    cout << S.get(l, r) << endl;
  }
}

#line 1 "test/library_checker/data_structure/static_range_sum_2.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <bits/stdc++.h>
using namespace std;
#line 2 "data_structure/sequence/invertible_cumulative_sum.hpp"
/**
 * @brief 可逆累積和
*/
template <typename T>
struct invertible_cumulative_sum{
  vector<T> S;
  function<T(T, T)> f;
  function<T(T)> inv;
  T E;
  invertible_cumulative_sum(){
  }
  invertible_cumulative_sum(vector<T> A, function<T(T, T)> f, function<T(T)> inv, T E): f(f), inv(inv), E(E){
    int N = A.size();
    S = vector<T>(N + 1);
    S[0] = E;
    for (int i = 0; i < N; i++){
      S[i + 1] = f(S[i], A[i]);
    }
  }
  T get(int i){
    return S[i];
  }
  T get(int l, int r){
    return f(S[r], inv(S[l]));
  }
};
#line 5 "test/library_checker/data_structure/static_range_sum_2.test.cpp"
int main(){
  int N, Q;
  cin >> N >> Q;
  vector<long long> a(N);
  for (int i = 0; i < N; i++){
    cin >> a[i];
  }
  invertible_cumulative_sum<long long> S(a, plus<long long>(), negate<long long>(), 0);
  for (int i = 0; i < Q; i++){
    int l, r;
    cin >> l >> r;
    cout << S.get(l, r) << endl;
  }
}