やみとものプログラミング日記 やみとものプログラミング日記
TOP Imos法 数列に対する区間addをO(1)で行う
Imos法 数列に対する区間addをO(1)で行う

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

競プロ アルゴリズム
作成日時: 2019年11月29日(金) 17時26分
更新日時: 2019年11月29日(金) 18時22分
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(数列のサイズ)なことに注意してください。

#cpp
#include
using namespace std;
class Imos
{
public:
vector seq;
vector 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_suint 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 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;
}
#cpp_end


コメント(0)

まだコメントがありません。
もしよろしければ下のフォームからコメント下さい。


コメントする

もしよろしければコメント下さい。

ハンドルネーム:

内容:

最新記事


【英語】テスト駆動勉強法
【英語】テスト駆動勉強法
コサイン類似度はベクトルを正規化してから内積を取っている
コサイン類似度はベクトルを正規化してから内積を取っている
【ゼロから作るDeep Learning 2】MatMulノード解説
【ゼロから作るDeep Learning 2】MatMulノード解説
『競プロ』カテゴリの記事