まえがき

atcoder.jp

ABC221 - D によって苦しめられたので imos 法を勉強しました。

値域の大きな imos 法についての名称が定まっていなかったのでとりあえず、動的 imos 法と名付けます。（動的セグメント木っぽさがあったように感じたので）

imos 法とは

imos 法は $[l, r)$ の区間にある値 $v$ を追加したいというときに用いるものです。

$N, Q \leq 10^{5}$
$l, r, v \leq N$

上記の制約で $Q$ 個の区間 $[l, r)$ に値 $v$ を追加したいような場合を考えてみます。

まずは、長さ $N$ 程度の配列 $A$ を用意して、 $A[l ] += v$ 、 $A[r ] -= v$ としておいて、あとで前から累積和をとっていくことで $A[i ]$ には $i$ の地点での値の合計が入っています

毎回、区間に値を一つずつ加算していく操作を愚直に行うと $O(NQ)$ ですが、imos 法を用いることで $O(N + Q)$ に改善できます。

値域が大きい場合

では、次のような例も考えてみます。

$N \leq 10^{9}$
$Q \leq 10^{5}$
$l, r, v \leq N$

先ほどの例と同様に長さ $N$ 程度の配列を用意しようとした時点で、使用するメモリが多すぎて、足りなくなってしまいます。

そこで、連想配列を用いて区間の端点のみ扱うことで使用するメモリ量を節約しながら値を求められます。

区間 $[l, r)$ を追加していき、前から累積和を取っていって、端点が持つ値を使用できます。

もしくは、区間を座標圧縮しておくことで前の例とほぼ同様に imos 法を適用できます。

実装

さて、ここまででお気持ちと理論は分かりました。

次に実装について細かい部分を考えていきます。

連想配列を使うよりも座標圧縮を行う方が簡単なので、そちらを使用します。

実際に注意して考えるべきなのは区間を扱う際の座標圧縮前後の値だけなので思ったよりは難しくありません。

※これより下部に書かれているコードは厳密ではないのでお気持ちだけ理解して下さい。

区間に値を挿入するパート

$l, r, v$ を受け取り、区間を扱う配列に追加します。

あとで座標圧縮をするため、値のみを扱う配列を別途用意して、区間の値を追加していきます。

// [l, r)
void add(T l, T r, T v) {
  sections.emplace_back(l, r, v);
  xs.emplace_back(l);
  xs.emplace_back(r);
}

累積和パート

区間の値を座標圧縮し、累積和を格納する配列に端点とその値を追加していきます。

追加し終えたら、累積和を行います。

void build() {
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  imos.assign(xs.size(), 0);

  for ( auto [l, r, v] : sections ) {
    l = lower_bound(xs.begin(), xs.end(), l) - xs.begin();
    r = lower_bound(xs.begin(), xs.end(), r) - xs.begin();
    imos[l] += v;
    imos[r] -= v;
  }

  for ( int i = 1; i < (int)imos.size(); i++ ) {
    imos[i] += imos[i - 1];
  }
}

値の受け取りパート

値の受け取りについてですが、

挿入された区間の最小値を $MIN$
挿入された区間の最大値を $MAX$

として、 $[MIN, MAX)$ を値が変化する部分で区切った配列を返すことにします。

より具体的には、 $[l_1, r_1) , [l_2, r_2), ... [l_Q, r_Q)$ （ $r_i = l_{i+1}$ を満たす）となるような区間と値のペアが入った配列を返します。

// vector<[l,r), value>
vector<pair<pair<T, T>, T>> section_values() {
  vector<pair<pair<T, T>, T>> res(xs.size() - 1);
  for ( int i = 0; i < (int)xs.size() - 1; i++ ) {
    T l = xs[i];
    T r = xs[i + 1];
    T v = imos[i];
    res[i] = make_pair(make_pair(l, r), v);
  }
  return res;
}

3 つのパートをまとめると、以下のようになります。

template <typename T>
struct dynamic_imos {
  vector<T> xs, imos;
  vector<tuple<T, T, T>> sections;
  dynamic_imos() {}

  // [l, r)
  void add(T l, T r, T v) {
    sections.emplace_back(l, r, v);
    xs.emplace_back(l);
    xs.emplace_back(r);
  }

  void build() {
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    imos.assign(xs.size(), 0);

<span class="synStatement">for</span> ( <span class="synType">auto</span> [l, r, v] : sections ) {
  l = lower_bound(xs.begin(), xs.end(), l) - xs.begin();
  r = lower_bound(xs.begin(), xs.end(), r) - xs.begin();
  imos[l] += v;
  imos[r] -= v;
}

<span class="synStatement">for</span> ( <span class="synType">int</span> i = <span class="synConstant">1</span>; i &lt; (<span class="synType">int</span>)imos.size(); i++ ) {
  imos[i] += imos[i - <span class="synConstant">1</span>];
}


  }

  // vector<[l,r), value>
  vector<pair<pair<T, T>, T>> section_values() {
    vector<pair<pair<T, T>, T>> res(xs.size() - 1);
    for ( int i = 0; i < (int)xs.size() - 1; i++ ) {
      T l = xs[i];
      T r = xs[i + 1];
      T v = imos[i];
      res[i] = make_pair(make_pair(l, r), v);
    }
    return res;
  }
};

使用例はこんな感じです。

int main() {
  int n;
  cin >> n;

  dynamic_imos<int> dimos;

  vector<P> ab(n);
  for ( auto &[a, b] : ab ) {
    cin >> a >> b;
    dimos.add(a, a + b, 1);
  }

  dimos.build();

  auto secs = dimos.section_values();

  vector<int> ans(n + 1, 0);
  for ( auto [section, value] : secs ) {
    auto [l, r] = section;
    ans[value] += r - l;
  }

  range(i, 1, n) cout << ans[i] << ' ';
  cout << ans[n] << endl;
}

あとがき

おつかれさまでしたー。

matumoto1234’s blog

動的なimos法について