test/cuml_sum.test.cpp

View this file on GitHub
Last update: 2024-05-04 20:54:20+09:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

algo/cuml_sum.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <bits/stdc++.h>
#include "../algo/cuml_sum.hpp"
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    CumlSum s(n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.assign(i, x);
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << s.sum(l, r) << endl;
    }
}

#line 1 "test/cuml_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <bits/stdc++.h>
#line 2 "algo/cuml_sum.hpp"
using namespace std;

template<typename T = long long>
struct CumlSum {
    CumlSum(size_t n) : _s(n + 1), _a(n), ready(false) {}
    CumlSum(vector<T> a) : _s(a.size() + 1), _a(a), ready(false) {}
    void assign(unsigned int p, T x) {
        if (_a[p] != x) ready = false;
        _a[p] = x;
    }

    // [l, r)
    // O(n * (calls after changes))
    T sum(unsigned int l, unsigned int r) {
        if (!ready) {
            for (int i = 0; i < (int) _s.size() - 1; i++) {
                _s[i + 1] = _s[i] + _a[i];
            }
            ready = true;
        }
        return _s[r] - _s[l];
    }
    private:
    vector<T> _s, _a;
    bool ready;
};
#line 4 "test/cuml_sum.test.cpp"
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    CumlSum s(n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.assign(i, x);
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << s.sum(l, r) << endl;
    }
}