ラムダ式を使ったsort

忘れがち
pairの要素でソートするときなどに使うかも。

second の降順、firstの降順でソート

    sort(K.begin(),K.end(),[](P const& a, P const& b){
        if(a.second != b.second) return a.second>b.second;
        return a.first > b.first;
    });

ACL segtree 忘備録

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

• 宣言のまえに

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

で、例えば「区間の最大値を要素に持つような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]

vector.back()をご存知でない！？

vector v={1,2,3,4};
とかってしたときの最後の要素にが欲しいとき、
v.back();
で要素が得られる。

sortのときとかは v.end()ってするけど、
あれはポインタなんですよね。

便利便利。

久しぶりに日記書いて書き方忘れてる。

2次元vector宣言

よく忘れるのでメモ

n行m列のベクターv、0で初期化

vector<vector<int>> v(n, vector<int>(m);

ノート 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 だったら大きいものから、みたいな。
比較条件は指定可能。

ノート

• c++ の文字列 string

・忘れずに using namespace std;
・宣言

string s; %普通に宣言
string s(N,'a'); %N文字、すべてaで初期化

・部分抜き出し

s.substr(0,3); %０文字目から３文字抜き出す

ノート priority_que, emplace_back,pop_count

• 優先度付きキュー　priority_que

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

priority_que<int> p;
p.push(1); // 1を追加
p.top(); //１番大きい要素を返す
p.pop(); //１番大きい要素を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)); //これと同じ（はず）

• ２進数表記したときの１の数　__builtin_popcount

__builtin_popcount(3); // = 2