Offline sum of linear segments （区間一次関数加算クエリの累積和を用いたオフライン処理）
(utilities/offline_sum_of_linear.hpp)

• View this file on GitHub
• Last update: 2022-01-08 20:23:44+09:00
• Include: #include "utilities/offline_sum_of_linear.hpp"

全ての項の値がゼロで初期化された数列 $[A_0, \dots, A_{N -1}]$ に対して以下のクエリを処理．

• $l \le i < r$ を満たす各 $i$ について $A_i$ に $f_0 + (i - l) \cdot df$ を加算．時間計算量 $O(1)$．
• $[A_0, \dots, A_{N - 1}]$ の値を陽に計算・取得．$O(N)$．

使用方法

offline_sum_of_linear<long long> f(N);
f.add_linear(l, r, f0, df);

long long vi = f[i]; // 特定の項の取得
vector<long long> values = f.vals(); // [f[0], ..., f[N - 1]] の一括取得

問題例

• AtCoder Regular Contest 125 E - Snack
• AtCoder Grand Contest 052 E - 3 Letters

Code

#pragma once
#include <cassert>
#include <tuple>
#include <vector>

// CUT begin
// Offline sum of linear segments
template <class T> struct offline_sum_of_linear {
    int N;
    std::vector<T> ret;
    std::vector<std::tuple<int, int, T, T>> upds;
    offline_sum_of_linear(int N_) : N(N_), ret(N_) {}

    // Add f0 + df * (x - l) to A[x] for x in [l, r)
    void add_linear(int l, int r, T f0, T df) {
        assert(0 <= l and l <= r and r <= N);
        if (l < r) upds.emplace_back(l, r, f0, df);
    }
    void run() {
        if (upds.empty()) return;
        std::vector<T> tmp(N + 1);
        int l, r;
        T f0, df;
        for (const auto &q : upds) {
            std::tie(l, r, f0, df) = q;
            tmp[l + 1] += df;
            tmp[r] -= df;
        }
        for (int i = 0; i < N; i++) tmp[i + 1] += tmp[i];
        for (const auto &q : upds) {
            std::tie(l, r, f0, df) = q;
            tmp[l] += f0;
            tmp[r] -= f0 + (r - l - 1) * df;
        }
        upds.clear();
        for (int i = 0; i < N; i++) tmp[i + 1] += tmp[i], ret[i] += tmp[i];
    }
    T operator[](int i) {
        assert(0 <= i and i < N);
        return run(), ret[i];
    }
    std::vector<T> vals() { return run(), ret; }
    int size() const { return N; }
    template <class OStream>
    friend OStream &operator<<(OStream &os, const offline_sum_of_linear &x) {
        auto y = x;
        y.run();
        os << '[';
        for (auto v : y.ret) os << v << ',';
        return os << ']';
    }
};

#line 2 "utilities/offline_sum_of_linear.hpp"
#include <cassert>
#include <tuple>
#include <vector>

// CUT begin
// Offline sum of linear segments
template <class T> struct offline_sum_of_linear {
    int N;
    std::vector<T> ret;
    std::vector<std::tuple<int, int, T, T>> upds;
    offline_sum_of_linear(int N_) : N(N_), ret(N_) {}

    // Add f0 + df * (x - l) to A[x] for x in [l, r)
    void add_linear(int l, int r, T f0, T df) {
        assert(0 <= l and l <= r and r <= N);
        if (l < r) upds.emplace_back(l, r, f0, df);
    }
    void run() {
        if (upds.empty()) return;
        std::vector<T> tmp(N + 1);
        int l, r;
        T f0, df;
        for (const auto &q : upds) {
            std::tie(l, r, f0, df) = q;
            tmp[l + 1] += df;
            tmp[r] -= df;
        }
        for (int i = 0; i < N; i++) tmp[i + 1] += tmp[i];
        for (const auto &q : upds) {
            std::tie(l, r, f0, df) = q;
            tmp[l] += f0;
            tmp[r] -= f0 + (r - l - 1) * df;
        }
        upds.clear();
        for (int i = 0; i < N; i++) tmp[i + 1] += tmp[i], ret[i] += tmp[i];
    }
    T operator[](int i) {
        assert(0 <= i and i < N);
        return run(), ret[i];
    }
    std::vector<T> vals() { return run(), ret; }
    int size() const { return N; }
    template <class OStream>
    friend OStream &operator<<(OStream &os, const offline_sum_of_linear &x) {
        auto y = x;
        y.run();
        os << '[';
        for (auto v : y.ret) os << v << ',';
        return os << ']';
    }
};

Back to top page