ACL segtree 忘備録

AtCoder Library 最近ようやく確認しました。
modintとか自分で実装しようとすると時間かかるやつがすぐ使えて(自分より)バグがなく使えるのほんとありがたい。
けど、公式の使い方資料わかりづらい。ということで、忘備録。(あとで公式資料リンク張る)
まずは "segtree" 
セグメント木ってやつですね。

  • 宣言のまえに

セグメント木の宣言のために、木の定義に使う二項演算 op単位元 eを宣言しておく必要がある。
細かいことは省くとして、ざっと以下のような感じ。
・二項演算:木の要素をどのように上るかのルールみたいなもの
単位元:「任意の木の要素 a 」vs 「単位元 e」で二項演算したときに、必ず a が返るような元。掛け算の1みたいな。

で、例えば「区間の最大値を要素に持つようなsegtree(要素はすべて正のint)」を考える場合は、こんな感じに先に定義しておく。

int op(int a, int b){ return max(a,b);}
int e(){return -1;}

以下、この op, e の segtree で説明する。


  • 宣言

2通りあるらしい。

#include <atcoder/all>
using namespace atcoder;

int N=4; //segtreeのサイズ
vector<int> v = {1,2,3,4}; //初期値にしたいベクトル

segtree<int, op, e> seg(N); //サイズNのsegtreeを宣言
segtree<int, op, e> seg(v); //初期値をv、サイズをv.size()とするsegtreeを宣言
  • 値の代入、取得
seg.set(i, 10); //seg[i] = 10 代入
seg.get(0); // seg[0]を取得
  • ある区間における目的の要素を取得

日本語難しい。
今のopの例だと、「ある区間における最大の要素を取得」することが高速にできる。
これが便利。

seg.prod(1,4); // 1≦i<4 における最大のseg[i]を取得。半開区間であることに注意
seg.all_prod(); // =seg.prod(0,N) 全区間に対して実行する場合はこれが使える
  • なんか条件を満たす区間の右端を探す的な

日本語難しい。
以下のようにすると、「i=l から右に見て行って、seg[i] < V を満たし続ける(seg[l]

int V=3;
bool f(int a){ return a<V ;} // 先に条件fを定義しておく
seg.max_right<f>(l);

上記のように、2段階で実行する。
なお、返ってくるrは半開区間のときのrであることに注意。
つまり [l,r)においてseg[i]