Imos法　数列に対する区間addをO(1)で行う

Imos法(いもす法)を初めて知ったとき、その強力さと実装の簡単さに驚きました。

Imos法

数列の区間に対する区間add(数列のある範囲に同じ数を足す)操作がO(1)でできるびっくり手法です。
もちろん区間addの符号を変えれば区間sub（数列のある範囲から同じ数を引く）操作もできます。
一通りの区間add操作のあと、O(数列のサイズ)の処理を行うことで数列の値を取り出すことができます。

ライブラリ(クラス)作った

簡単に使えるようにライブラリを作りました。この記事の最後にコードを貼っておきます。
検証した問題はC - AtColorです。

ライブラリの説明

ライブラリ(Imosクラス)は下のコードのように使用できますが、簡単に注意点などを説明しておきます。
まず、高速に区間add操作をしたい数列(10^7くらいのサイズの数列までOK)のサイズを指定して以下のようにインスタンスを用意します。

Imos imos(1000001);

ここで用意される数列は0-indexed、つまりインデックスは0から始まることに注意
その後、その数列への区間add操作は以下のようにできます。
区間の指定方法が[start, end)なことに注意してください。

imos.range_add(addするインデックスの開始値, addするインデックスの終了値+1, addする値);

区間addが一通り終わったらcalcメソッドを実行し、get_max,get_valなどで最大値や数列の値を取得できます。
calcを同時にしてしまうget_max_with_calcやget_val_with_calcというメソッドもありますが、これらのメソッドはO(数列のサイズ)なことに注意してください。

#include <bits/stdc++.h>

using namespace std;

class Imos
{
public:
    vector<int> seq;
    vector<int> temp;

    /*
        指定されたsizeのimos配列を作る(0-indexed)
    */
    Imos(int size) {
        seq.resize(size);
    }

    /*
        [start, end)にvalを足す
        O(1)
    */
    void range_add(int start, int end, int val) {
        seq[start] += val;
        seq[end] -= val;
    }

    /*
        [start, end)にvalを引く
        O(1)
    */
    void range_sub(int start, int end, int val) {
        range_add(start, end, -val);
    }

    /*
        数列の最大値を取る
        取るたびに毎回数列を舐める処理をするのでO(size)
    */
    int get_max_with_calc() {
        calc();
        return *max_element(temp.begin(), temp.end());
    }

    /*
        数列の最小値を取る
        取るたびに毎回数列を舐める処理をするのでO(size)
    */
    int get_min_with_calc() {
        calc();
        return *min_element(temp.begin(), temp.end());
    }

    /*
        数列の最大値を取る
        calcの後に呼び出すことを前提とする
        calcはO(size)だが、その後のget_maxはO(1)
    */
    int get_max() {
        return *max_element(temp.begin(), temp.end());
    }

    /*
        数列の最小値を取る
        calcの後に呼び出すことを前提とする
        calcはO(size)だが、その後のget_minはO(1)
    */
    int get_min() {
        return *min_element(temp.begin(), temp.end());
    }

    void calc() {
        int size = seq.size();
        temp.resize(size);
        temp[0] = seq[0];
        for (int i=1; i<size; i++) {
            temp[i] = temp[i-1] + seq[i];
        }
    }

    int get_val_with_calc(int i) {
        calc();
        return temp[i];
    }

    int get_val(int i) {
        return temp[i];
    }
};

int n;
int a, b;

int main()
{
    cin >> n;
    
    Imos imos(1000001);

    for (size_t i = 0; i < n; i++)
    {
        cin >> a >> b;
        imos.range_add(a, b + 1, 1);
    }
    
    cout << imos.get_max_with_calc() << endl;
}