verify/verify-yosupo-ds/yosupo-static-sum.test.cpp

• View this file on GitHub
• Last update: 2025-03-29 17:57:48+08:00
• Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

• src/alfred/config/io-sync-off.hpp
• src/alfred/data_structure/sum.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/static_range_sum

#include "../../src/alfred/config/io-sync-off.hpp"
#include "../../src/alfred/data_structure/sum.hpp"
#include <iostream>

int main(int argc, char const *argv[]) {
    int n, q, l, r;
    optimizeIO(), std::cin >> n >> q;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    Sum<long long> S(a);
    while (q--) {
        std::cin >> l >> r;
        std::cout << S.query(l, r - 1) << '\n';
    }

    return 0;
}

#line 1 "verify/verify-yosupo-ds/yosupo-static-sum.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/static_range_sum

#line 1 "src/alfred/config/io-sync-off.hpp"
#include <bits/stdc++.h>

inline void optimizeIO(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL), std::cout.tie(NULL);
}
#line 1 "src/alfred/data_structure/sum.hpp"



#line 6 "src/alfred/data_structure/sum.hpp"

template <class T>
class Sum {
private:
    int n;
    std::vector<T> _pre, _suf;

public:
    Sum(void) : n(0) {}
    template <class InitT>
    Sum(std::vector<InitT> &_init) { init(_init); }
    template <class InitT>
    inline void init(std::vector<InitT> &_init) {
        if (_init.empty()) return;
        _pre.resize(n = _init.size()), _suf.resize(n);
        _pre[0] = _init[0], _suf[n - 1] = _init[n - 1];
        for (int i = 1; i < n; i++) {
            _pre[i] = _pre[i - 1] + _init[i];
        }
        for (int i = n - 2; i >= 0; i--) {
            _suf[i] = _suf[i + 1] + _init[i];
        }
    }
    inline T query(int l, int r) {
        if (l > r) return T();
        return l == 0 ? _pre[r] : _pre[r] - _pre[l - 1];
    }
    inline const T pre(int x) { return _pre[x]; }
    inline const T suf(int x) { return _suf[x]; }
};

template <class T>
class GridSum {
private:
    size_t n, m;
    std::vector<std::vector<T>> sum;

public:
    GridSum(void) : n(0), m(0) {}
    template <class InitT>
    GridSum(std::vector<std::vector<InitT>> &_init) { init(_init); }
    template <class InitT>
    inline void init(std::vector<std::vector<InitT>> &_init) {
        if (_init.empty()) return;
        n = _init.size(), m = _init[0].size();
        sum.assign(n, std::vector<T>(m)), sum[0][0] = _init[0][0];
        for (size_t i = 1; i < n; i++) {
            sum[i][0] = sum[i - 1][0] + _init[i][0];
        }
        for (size_t i = 1; i < m; i++) {
            sum[0][i] = sum[0][i - 1] + _init[0][i];
        }
        for (size_t i = 1; i < n; i++) {
            for (size_t j = 1; j < m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + _init[i][j];
            }
        }
    }
    inline T query(int x1, int y1, int x2, int y2) {
        T s1 = x1 == 0 ? 0 : sum[x1 - 1][y2];
        T s2 = y1 == 0 ? 0 : sum[x2][y1 - 1];
        T s3 = x1 == 0 || y1 == 0 ? 0 : sum[x1 - 1][y1 - 1];
        return sum[x2][y2] - s1 - s2 + s3;
    }
};

template <class T>
class SubsetSum {
private:
    int n;
    std::vector<T> sum;

public:
    SubsetSum(void) : n(0) {}
    template <class InitT>
    SubsetSum(std::vector<InitT> &_init)
        : n(_init.size()), sum(_init) { init(_init, true); }
    template <class InitT>
    inline void init(std::vector<InitT> &_init, bool internal = false) {
        if (!internal) {
            n = _init.size(), sum = _init;
        }
        for (int i = 0; (1 << i) <= n; i++) {
            for (int S = 0; S < n; S++) {
                if (S >> i & 1) sum[S] += sum[S ^ (1 << i)];
            }
        }
    }
    inline T query(int mask) { return sum[mask]; }
};


#line 6 "verify/verify-yosupo-ds/yosupo-static-sum.test.cpp"

int main(int argc, char const *argv[]) {
    int n, q, l, r;
    optimizeIO(), std::cin >> n >> q;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    Sum<long long> S(a);
    while (q--) {
        std::cin >> l >> r;
        std::cout << S.query(l, r - 1) << '\n';
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	121 ms	13 MB
g++	max_random_01	AC	128 ms	13 MB
g++	max_random_02	AC	123 ms	13 MB
g++	max_random_03	AC	125 ms	13 MB
g++	max_random_04	AC	121 ms	13 MB
g++	random_00	AC	105 ms	11 MB
g++	random_01	AC	114 ms	12 MB
g++	random_02	AC	72 ms	4 MB
g++	random_03	AC	34 ms	12 MB
g++	random_04	AC	38 ms	9 MB

Back to top page