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]

ノート set, deque, queue, priorty_queue

  • set

要素を格納して、後からある要素が含まれているか確認したいようなときに使うコンテナ
set - cpprefjp C++日本語リファレンス

ABC176E の爆弾の位置をvectorで扱おうと思ったらTLEしたりREしたりした。
(REはおそらくメモリが足りなかった)

set<int> a; %宣言

a.emplase(1); %要素の追加 emplase以外にもあったはず
a.emplase(2);

a.find(1); %1という要素があればそのイテレータを返す なければend()が帰る
a.contain(1); %1という要素があるかのbool
a.count(1); %1という要素の数
  • deque

キューを格納して順に処理してくみたいなときに使う。
先頭・終端への追加・削除が可能
deque - cpprefjp C++日本語リファレンス

  • queue

dequeと似ている(?)が、先頭への追加・削除しかできない。FIFO

  • priority_queue

dequeと似ている(?)が、要素のうち優先度が高いものから取り出される。
int だったら大きいものから、みたいな。
比較条件は指定可能。

ノート priority_que, emplace_back,pop_count

  • 優先度付きキュー priority_que

優先度の高いものへのアクセスが早い

priority_que<int> p;
p.push(1); // 1を追加
p.top(); //1番大きい要素を返す
p.pop(); //1番大きい要素をpop
  • コンストラクタ+push_back emplace_back

型の違うvectorとかに入れるときに楽

vector<pair<int,int>> p;
p.emplace_back(1,2); // pair<int,int>(1,2)をpush_back
p.push_back(pair<int,int>(1,2)); //これと同じ(はず)
  • 2進数表記したときの1の数 __builtin_popcount
__builtin_popcount(3); // = 2