offset_manager
(Datastructure/offset_manager.hpp)

• View this file on GitHub
• Last update: 2024-07-06 20:37:29+09:00
• Include: #include "Datastructure/offset_manager.hpp"

概要

データ構造に対し、登録されている値全体へのaddをO(1)で可能にするための補助構造体。
offset(補正値)を管理する。

注意

inf(10 ^ 18)を 10 ^ 5回add とかするとオーバーフロウで壊れる

集約値への反映

sum … 変換値のsum + offset * データ個数

max … 変換値のmax + offset

• 個数制限付きナップザック(limited_knapsack)はこれを用いた。

Code

TT struct offset_manager {
    T offset;

    offset_manager() {
        offset = T();
    }

    void add_all(T x) {
        offset += x;
    }

    T push(T x) {// 生の値 → 補正値
        return x - offset;
    }

    T pop(T x) {// 補正値 → 生の値
        return x + offset;
    }
};

/*
@brief offset_manager
@docs doc/offset_manager.md
*/

#line 1 "Datastructure/offset_manager.hpp"
TT struct offset_manager {
    T offset;

    offset_manager() {
        offset = T();
    }

    void add_all(T x) {
        offset += x;
    }

    T push(T x) {// 生の値 → 補正値
        return x - offset;
    }

    T pop(T x) {// 補正値 → 生の値
        return x + offset;
    }
};

/*
@brief offset_manager
@docs doc/offset_manager.md
*/

Back to top page