2020年11月15日15時58分44秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．

cLay概要（version 20201115-2）

概要

C++っぽい言語をC++言語に変換します．
無駄にライブラリを張るのがめんどくさい，鬱陶しい，ライブラリを整備していても綺麗に書けない処理があるなどを解消したいというのが目的．目的の達成はそのうち…．
blogにコード載せる時にライブラリとかincludeとかが長ったらしい，のをなんとかしたいというのも動機の1つです．

#include<bits/stdc++.h>およびgetchar_unlocked，putchar_unlockedなどを使用しているので，それが動かない環境だと動かないし，動かないコードが出てきます．
（その場合は，フラグの欄を見て下さい）

コードの公開ページはこちら．C++っぽいコードを標準入力から食わせるとC++のコードが標準出力から出てきます．

細かいバージョンアップの際には，ドキュメント（本ページ）は更新されないかもしれません．
過去のバージョンの情報は，そのときの最新のドキュメントにリンクを張っていますので，ここに情報がない場合は，最新のバージョンのページも参照してください．

未対応なもの

重要度が高い順に，下線付き太字，太字，普通です．重要度が低いものはそもそも対応させる気がないものが多いです．
この欄ではC++ではできるけど…というもの主にリストアップ．

制限

以下の単語は変数名などで使うとやばい．
基本的にバージョンアップするときは互換性を保ちたいけど，此処の欄は普通に増やす．

chmax, chmin,
ll, ull, mint, segtree, combination_mint,
rd, reader,
wt, wtLn, wtSp, wtN, wtF, wt_L, writer, writerLn, writerSp, writerN, writerF,
min, max, argmin, argmax, argminL, argmaxL,
gcd, GCD, lcm, LCM, sum, SUM, mul, MUL,
sortA,
reduceFraction, runLength,
wmem, memarr,
malloc1d, malloc2d, free1d, free2d, walloc1d, walloc2d,
int_inf, ll_inf, double_inf, MD, PI

intは32bit，longは32bitか64bit，long longは64bitだと思って実装しています．違うとまずい場合があるかも．

色々

最初に

#include<bits/stdc++.h>
using namespace std;

が強制的に挿入されます．
#includeを書く必要はないですが，GCC以外で動かなくなる．

int main()は省略可能です．
いきなり関数の中じゃなくて{で始まるブロックが最初に出てきたときにint main()が補われます．
int main()で補われたブロック内の最後がreturn文でない場合は，return 0;が最後に補われます．

変数宣言や三項演算子 ? : を使っていない部分での,は（適切に{}を補った上で）;に置き換えられます．
その結果，for(;;) i++, break; などと書くと for(;;){ i++; break; } に展開されます．

フラグ

途中で（プログラムの先頭が推奨）
//hogehoge
という形式でフラグを立てておくと色々な環境に対応させるために出力されるコードが変更されます．

またmint構造体など使用すると挿入される関数や構造体を挿入されなくするフラグは以下の通りです．
例えば，//no-insert-mintを指定するとmint型が使えなくなる代わりに，mintという変数や関数などを自由に宣言することができるようになります．

型

ll は long long に，ull は unsigned long long に置き換えられます．
VI は vector<int> に，VII は vector<vector<int>> に，VIII は vector<vector<vector<int>>> に置き換えられます．

mint型が使えます．
mod MDで計算します（MDは#define MD hogeで定義しなければデフォルトでは10^9+7が使用されます．MDは奇素数でなければ上手く動かない可能性があります．定数の項も参照のこと）．
四則演算（割り算も）は使えます．int型やll型などと計算すると結果はmint型になります．
mint型の法の設定などはmain関数の変数宣言後に行うので，変数宣言時に代入などすると上手く動かないので，変数宣言時に代入するのは避けたほうが良いです．
mint x; x = 1; x /= 2; wt(x); で 500000004 が表示されます．
また，べき乗 pw が使えます．
mint x, p; x = 2; p = x.pw(100); で p に $2^{100} \bmod (10^9+7)$ が代入されます．
mint x; x.setmod(1000000009); とすることで，途中で mod の値を変えることができます．
mintの詳しい仕様はそのうち書きます．

モンゴメリ乗算を使用しないmodint型もあります．
MDが素数でなくても，割り算をしなければmodint型は動くと思います．
mint型とmodint型はほぼ同じ使用方法です．

途中で mod を変更できないバージョンとして1文字目を大文字にした Mint, Modint があります．
こっちのほうが高速なはず．初期化も必要ないので，変数宣言時に代入しても大丈夫なはず．
mint, modint, Mint, Modint はコンストラクタで 0 に設定されるはずです．

入出力1

unlocked シリーズが使えない場合は，//no-unlocked フラグを指定してください．unlocked じゃないものを利用します．

rd(i, j, k)で標準入力からi,j,kが読み込まれます．scanf("%d%d%d",&i,&j,&k);などと似た感じですが，スペース区切りじゃなく，数字以外で区切られます．
rd(i, j(n), k)はrd(i, j[0], j[1], ..., j[n-1], k)に置き換わります（左から処理するのでrd(n, A(n))とか可能です）．
また，rd(N, (A,B)(N)) は rd(N, A[0], B[0], A[1], B[1], ..., A[N-1], B[N-1]) に置き換わります．グラフのエッジの入力とかに．
2次元の入力は rd(arr(3,3)) で rd(arr[0][0], arr[0][1], arr[0][2], arr[1][0], arr[1][1], arr[1][2], arr[2][0], arr[2][1], arr[2][2]) になります．3次元以上も同様．
rdの代わりにreaderでもOK．
rdは今のところint型，unsigned型，ll型，ull型，double型（指数表記は対応していない），mint型，char型（1文字），char型の配列（文字列），string型，vector<T>，Matrix<T>，Permutation，IntMap，Grid1d<T>，Grid2d<T>にのみに対応．ただし，Tは対応している型でなければならない．他の型もそのうち対応．
また，char S[1000]; int N; rd(S@N);で文字列 S を読み込むと同時に文字列の長さを N に代入します．複数の文字列の場合は char S[10][1000]; int N[10]; rd(S@N(10)); とS@Nはひとかたまりで扱います．
char型1文字の入力の場合も，空白などは読み飛ばして，次の空白でない文字を読み込みます．

rd(i--) は rd(i); i--; になります．++もできます．2減らすなら rd(i----) です．
rd((A--)(N)) は配列AのN個の要素すべてが1減ります．カッコは必須です．rd(A--(N)) は書けません．
rd((A--,B--,C)(N)) は配列A，Bの要素は1減り，Cの要素はそのままです．
1-originから0-originに直しながら入力するときなど．

A[2], B[4], A[3], B[5], A[4], B[6] に読み込みたい場合は rd(((A+2),(B+4))(3)); で可能です．
A[2], A[3], A[4] に読み込む場合は rd(((A+2))(3)); で可能です（かっこが多すぎる気がしますが，現状これだけ必要です…：(A+2)[0], (A+2)[1], (A+2)[2]でアクセスします）．

int len; char buf[100];
len = rdLine(buf); で1行の読み込みを行います．
正確には，\n か EOF に出くわすまでbufに入れていきます（\nは入らない）が，\rだけは無視されます．
lenには基本的に読み込んだ文字数を返しますが，1文字も読み込まずEOFに出くわした場合のみ-1を返します．
bufの最後の文字の次に \0 を入れて返します．

変数に代入しないものとして，以下の関数は次の入力をその型の値として戻り値で返します．

wt(i, j, k)でスペース区切りでi, j, kを標準出力に吐き出し，改行します．
wt(i, j(n), k)はwt(i, j[0], j[1], ..., j[n-1], k)に置き換わります．
また，wt(N, (A,B)(N)) は wt(N, A[0], B[0], A[1], B[1], ..., A[N-1], B[N-1]) に置き換わります．式の一部がこの形でも同様に置き換わります（以下の例を参照）．
最後に改行する代わりにスペースを出力する場合はwtの代わりにwtSpを，改行区切りで出力する場合はwtLnを使います．また区切りに何も出力しない場合はwtNを使います．
wtの代わりにwriter，wtSpの代わりにwriterSp，wtLnの代わりにwriterLnでもOK．
wtは今のところint型，ll型，double型，mint型，char型の配列（文字列），string型のみに対応．他の型もそのうち対応．
（ただし，string型は参照渡し．変数に代入せずにそのまま渡すときは .c_str() をつけるとchar型の配列で出力できると思われます）
wtFは文字列を出力しますが，変数名を{}で囲むと，その変数の値に置換されて出力されます．文字列中で{または}を出力したい場合はエスケープして\{または\}と書きます．

関数 wt(f(a)) は，fが変数として認識されてないと f(0), f(1), ..., f(a-1) に展開されませんが，fが変数として認識されていると展開してしまいます（特に構造体を作ってその変数fを定義している場合）．
配列の展開しない場合，Wt(f(a)) や Writer(f(a)) のように W を大文字にしてください．

double型の変数を wt() で出力する場合，デフォルトでは小数点以下15桁表示します．
10桁表示したい場合は，事前に writerDigit_double(10); としてください．
また，現在の表示桁数を取得する場合は，writerDigit_double(); で取得できます．
中身が NaN, Inf などの変数を表示させた場合，現状は Err と表示されます．

2次元以上の配列の出力は，wtLn など区切り文字を明示的に指定したものを使うと各要素がそれで区切られます．
wt を使った場合，配列単体を出力する場合，および，出力の最後が配列の場合は，配列の最後のインデックスに対して1行に出力されます．
wt(arr(2,3)) の場合は，
arr[0][0] arr[0][1] arr[0][2]
arr[1][0] arr[1][1] arr[1][2]
となり
wt(arr(2,2,3)) の場合は
arr[0][0][0] arr[0][0][1] arr[0][0][2]
arr[0][1][0] arr[0][1][1] arr[0][1][2]
arr[1][0][0] arr[1][0][1] arr[1][0][2]
arr[1][1][0] arr[1][1][1] arr[1][1][2]
と出力されます．最後の要素でない場合は，1行に出力されます．
wt(arr(2,3), "hoge", 100) の場合は
arr[0][0] arr[0][1] arr[0][2] arr[1][0] arr[1][1] arr[1][2] hoge 100
です．

また，出力に関してオプションで B=n と指定すると整数系のものは n 進数で出力されます．
例えば，wt[B=3]("hello", 10); は hello 101 と出力されます（文字列に関しては基数は無視されます）．
62進数まで指定可能で，文字は 01...9ABC...Zabc...z の順番です．

例:

int N, A[10], B[10], res[10];
rd(N, (A,B)(N));
wt(N, 2*res(N)+1);

は以下と同じ意味になります．

int i, N, A[10], B[10], res[10];
scanf("%d", &N);
for(i=0;i<N;i++) scanf("%d%d", A+i, B+i);
printf("%d ", N);
for(i=0;i<N;i++) printf("%d%c", 2*res[i]+1, i==N-1?'\n':' ');

また

int T = 0, res = 10;
wtF("\{Case {++T}: {res}\}\n");

は以下と同じ意味になります．

int T = 0, res = 10;
printf("{Case %d: %d}\n", ++T, res);

また

int N, L[10];
char S[10][1000];
rd(N, S@L(N));

は以下と同じ意味になります．

int i, N, L[10];
char S[10][1000];
scanf("%d",&N);
for(i=0;i<N;i++){
  scanf("%s",S[i]);
  L[i] = strlen(S[i]);
}

標準入出力ではない場合は，readerFile()，writerFile()を利用して入出力先を指定します．
ファイル名（勝手にfopen, fcloseされる）かファイルポインタを引数に指定します．

  int i, j, k;

  rd(i); // stdinから読み込み
  readerFile("input.txt");
  rd(j); // input.txtから読み込み
  readerFile();
  rd(k); // stdinから読み込み

  wt(i); // stdoutに書き込み
  writerFile("output.txt");
  wt(j); // output.txtに書き込み
  writerFile("log.txt", "a");
  wt(k); // log.txtに追加で書き込み "a"モードで開く
  writerFile(stderr);
  wt("hoge"); // stderrに書き込み

入出力2

変数を宣言した際に変数名の前に@をつけると，その時点でrd()を利用して入力します．
現状，配列などは対応していないし，読み込むついでにインクリメント，デクリメントする（++, --）など対応していません．

{
  int @A, @B, res = abs(A-B)/+10;
  wt(res);
}

は

{
  int A;
  rd(A);
  int B;
  rd(B);
  int res = abs(A-B)/+10;
  wt(res);
}

となります．

ループ

rep(n) は int hoge; for(hoge=0;hoge<n;hoge++) に置き換えられます（hogeは適当な変数名）．
rep(i,n) は for(i=0;i<(n);i++) に置き換えられます．
rep(i,a,b) は for(i=(a);i<(b);i++) に置き換えられます．
rep(i,a,b,s) は for(i=(a);i<(b);i+=(s)) に置き換えられます．
REP(n) は int hoge, piyo = n; for(hoge=0;hoge<piyo;hoge++) に置き換えられます（hoge, piyoは適当な変数名）．
REP(i,n) は int piyo = n; for(i=0;i<piyo;i++) に置き換えられます（piyoは適当な変数名）．
REP(i,a,b) は int piyo = b; for(i=(a);i<piyo;i++) に置き換えられます（piyoは適当な変数名）．
REP(i,a,b,s) は int piyo = b, huga = s; for(i=(a);i<piyo;i+=huga) に置き換えられます（piyoは適当な変数名）．
また，この際，変数iが宣言されていなかった場合，勝手にint型の変数として宣言されます．
rep では終了条件の変数・式 (n, b) が複数回評価されたり，ループの中で書き換え可能ですが，REP はそうではないことに注意してください．

同じ範囲をループで逆順で回す場合は以下があります（sを指定した場合，必ずしも同じ範囲ではないかもしれない）．
rrep(n) は int hoge; for(hoge=(n)-1;hoge>=0;hoge--) に置き換えられます（hogeは適当な変数名）：使う意味はないです．
rrep(i,n) は for(i=(n)-1;i>=0;i--) に置き換えられます．
rrep(i,a,b) は for(i=(b)-1;i>=(0);i--) に置き換えられます．
rrep(i,a,b,s) は for(i=(b)-1;i>=(a);i-=(s)) に置き換えられます．
RREP(n) は int hoge, piyo = n; for(hoge=piyo-1;hoge>=0;hoge--) に置き換えられます（hoge, piyoは適当な変数名）：使う意味はないです．
RREP(i,n) は int piyo = n; for(i=piyo-1;i>=0;i--) に置き換えられます（piyoは適当な変数名）．
RREP(i,a,b) は int piyo = a; for(i=(b)-1;i>=piyo;i--) に置き換えられます（piyoは適当な変数名）．
RREP(i,a,b,s) は int piyo = a, huga = s; for(i=(b)-1;i>=piyo;i-=huga) に置き換えられます（piyoは適当な変数名）．

配列の中身を変数に代入して使用したい場合は，例えば rep[arr](i,n) hoge; および rep[arr](i,n){ hoge; } は

rep(tekitouna_namae, n){
  auto &i = arr[tekitouna_namae];
  hoge;
}

に展開されます．rep, REP, rrep, RREP それぞれ，引数の数も自由です．
また，インデックスも利用する場合，例えば rep[arr,ind](i,n) hoge; および rep[arr,ind](i,n){ hoge; } は

rep(ind, n){
  auto &i = arr[ind];
  hoge;
}

に展開されます．
変数 i は既に宣言されていても，ブロックの中で再び定義されます．

ループから抜ける break について，二重ループから抜ける break_break などがあります．
break_break は break した後，その直後に break したのと同じ挙動になるはずです．
3重ループを抜ける break_break_break や，一つ上のループに対して直接continueをする break_continue などがあります．
break_ を何回か繰り返して break または continue を最後に付けた文があり，break_A は break を行って，ループを抜けた直後に A を行う感じです．

また，括弧内（(),[],{}のどれか）で2つ以上のドットで区切ると範囲を指定でき，勝手にループに展開されます．
ドットの数が等しいものが同じ変数だと思われて，同じドットの数のものは2回目以降に登場したときには区間の終わりは省略可能です．
（ドットの数が少ない方が内側のループになります．2次元配列のアクセス順で速度がかなり変わるので気をつけたほうが良い場合があります）
例えば，単位行列を作るコード，行列のコピーのコード，転置しながらコピーするコードは

int A[10][10], B[10][10], C[10][10];
A[0...9][0..9] = 0;
A[0..9][0..9] = 1;
B[0...9][0..9] = A[0...9][0..9];
C[0...9][0..9] = A[0..9][0...9];

のように書け，これは

int i, j, A[10][10], B[10][10];
for(i=0;i<=9;i++) for(j=0;j<=9;j++) A[i][j] = 0;
for(i=0;i<=9;i++) A[i][i] = 1;
for(i=0;i<=9;i++) for(j=0;j<=9;j++) B[i][j] = A[i][j];
for(i=0;i<=9;i++) for(j=0;j<=9;j++) C[i][j] = A[j][i];

と同値です（B[0...9][0..9] = A[0...9][0..9];はB[0...9][0..9] = A[0...][0..];と書くこともできます）．

括弧で囲まれていなければならないことに注意して下さい．

A[0..9] = (0..9)
B[0..9] = 50 - (23..)

は

for(i=0;i<=9;i++) A[i] = i;
for(i=0;i<=9;i++) B[i] = 50 - (23 + i);

と同値ですが， A[0..9] = 0..9; などとは書けません．

文字列の中に2個以上ドットが並ぶとバグる実装なのでそのうちなんとかする．

特殊なループ（多重ループ）

たとえば，

int d[10], n = 10;
rep_perm(d,n){
  hoge;
}

は

int d[10], n = 10;
for(int tmp = 0; tmp < n; tmp++){
  d[tmp] = tmp;
}
do{
  hoge;
} while(next_permutation(d, d+n));

に置換されます．
他のもだいたい同様で，辞書順最小のものからループします．
（重複を許さない組合せで n より m のほうが小さい場合（条件を満たす配列が存在しない場合）は，ループの中身は1回も実行されません）
このループに使用する，next_permutation() に相当する，条件を満たす配列で，辞書順で次のものを求める関数 scomb(), mcomb(), sarr(), marr() 等もあり以下のとおりです．

hoge は rep_piyo の説明を参照．

演算子

昔のGCC拡張で存在した<?および>?演算子の同時に代入するバージョンのみ使えます．
つまり，a <?= b; は a = min(a, b); と，a >?= b; は a = max(a, b); と大体同じです．
代入しないバージョンは素直にminおよびmaxを使え．

正の整数に関する繰り上げの割り算演算子 /+ が使えます．
13 /+ 3 は 5 となります．
実際には a /+ b は (a+b-1) / b で定義され，正の整数でないと繰り上げ割り算になる保証はありません．
また，a+b-1 がオーバーフローする可能性があるので要注意です．
a = a /+ b; は a /+= b; と書くこともできます．
負などもありうる場合には以下の関数が使えます．

負の数を正の数で割った余りを非負の数で返す %% 演算子があります．
(-5) %% 2 は 1 になります．
演算子の優先順位が低いので，-5 %% 2 は-(5 %% 2) = -1になります．
a = a %% b; は a %%= b; と書くこともできます．

べき乗演算子 ** が使えます．
2 ** 3 は $2^3 = 8$ を表します．
点 (x1, y1) と (x2, y2) とのユークリッド距離は sqrt( (x1-x2)**2 + (y1-y2)**2 ) と簡潔に書けるようになります．
バイナリ法を使用します．
x ** y において，y は非負整数である必要があって，結果の型は x の型と同じになります（y が非負整数じゃない場合は標準の pow 関数などを使って下さい）．
ただし，x, y ともに double 型のときは，標準の pow(x,y) が呼び出されます．
a = a ** b; は a **= b; と書くこともできます．

数値の後の掛け算の演算子*は省略できることがあります．
z = 2 2x+2(x+5); で z = 2 * 2 * x + 2 * (x+5); の意味になります．
他の解釈ができる場合は*を省略できません．
2u は 2*u ではなくunsigned 型の定数 2 で，3d1 は 3*10 = 30 を表す整数で 3 * d1 などにはなりません．
数値はアルファベットで終わっている場合は，*を（現状では）省略できません．
z = 2u x; は駄目です．
また，数値の後以外の*の省略は（現状では）できません．
例えば，x(x+y) や (2)(x+y) に * が補われることはありません．
また，単純に*が補われるだけなので，x=2 のときに 7%2x は 7%2*x=1*2=2 となることに注意してください（7%(2x)ではない）．

等式，不等式の条件を続けるときに && を省略できます．
if(5 < x+y < 10) は if(5 < x+y && x+y < 10) に置き換わります．
if(i <= 5 < k <= 12 > j != m == n) は if(i <= 5 && 5 < k && k <= 12 && 12 > j && j != m && m == n) に置き換わります．
if(5 < x++ < 10) は if(5 < x++ && x++ < 10) に置き換わるので注意してください．
ただし，< hoge > の場合は，テンプレート絡みなどで使用することがあるので，この場合のみ展開されません．

(a1,a2,...,an) += (b1,b2,...,bn); または (a1,a2,...,an) += b; の形で複数の演算を一度に行います．
コンマ演算子をオーバーロードしていると変なことが起こるかもしれないので，この機能を無効化する場合は //no-arraylike-operations のフラグを指定してください．
具体的には，
(a,b) = (b,a+b);
は
{
auto tmp1 = b;
auto tmp2 = a+b;
a = tmp1;
b = tmp2;
}
と展開され，(a,b) += k; は
{
auto tmp = k;
a += k;
b += k;
}
と展開されます．
現状は，左辺は()で囲まれカンマ区切りで n 個 (n ≥ 2) の変数 (左辺値) がある場合，右辺は括弧で囲まれない 1 個の式か，括弧で囲まれた 1 個または n 個の式である必要があります．
また，演算子には = が含まれている必要があります．単項演算は現状非対応です．
a = b = 0 のとき，(a,b)+=(2,1); をやると a=2, b=1になりますが，C++ではa=0, b=1となります．結果が変わるので注意してください．

定数

int_inf は 1073709056 ($2^{30}-2^{15}$) に，
ll_inf は 4611686016279904256LL ($2^{62}-2^{31}$) に，
double_inf は 1e150 に置換されます．

int_infおよびll_infはそれぞれ2倍してちょっとした数を足してもint型，long long型でオーバーフローしないという値に設定しています．
また，double_infは2乗してもオーバーフローしないという値に設定しています．

また，MDは1000000007（$10^9+7$）に，PIは3.14159265358979323846（円周率）に置換されます（厳密には最初に#define MD 1000000007などが追加されます）．
MDとPIはコード中で #define MD 1000000009 などと言う記述が出てきたら置換されずそちらが優先されます．

また，double型の定数の書き方 1e-5 などと同様に，整数型の定数を 1d5 などと書けます．
$x$d$y$ で $\lfloor x \times 10^y \rfloor$ を表します．
$2^{31}$ 未満であれば int 型，$2^{31}$ 以上であれば ll 型，$2^{63}$ 以上であれば ull 型の定数になり，$2^{64}$ 以上の値だと上手く動きません．
$y$ は整数で $-30$ 以上 $30$ 以下でないと正しく動きません．

ワーキングメモリ

ワーキングメモリを必要な関数や機能などを使うと勝手にワーキングメモリを確保します．
void *wmem; に（デフォルトで）96,000,000バイトのメモリが確保されます．
サイズを変更する場合は，どこか（の行頭）で，
//working_memory=500MB
などと書くと500*1024*1024バイトのメモリになります．
//working_memory=500m
//working_memory=524288000
も同じ意味です．Bは省略可能，K,M,Gが接頭語として使えます．

行列

行列は Matrix<mint> m; などで定義します．
m[0][1] で0行1列の成分にアクセスできます（行番号，列番号は0から始まる）．
行列の足し算，引き算，かけ算は+，-，*でできます．べき乗演算子 ** なども使えます．定義できない演算をすると0行0列の行列になります．
int, ll, doubleの定数倍も可能です．
m = 1; などと定数を代入すると対角成分が1に，それ以外は0になります．
以下は Matrix<T> でに関してです．

コンストラクタ

その他

置換

置換は Permutation p; などで定義します．
p[i] = j は第i要素を第j番目に飛ばす，という意味です．
i も j も 0-origin です．
現状 p ** n の計算は（他の型と同様に）バイナリ法です．

コンストラクタ

デストラクタ

演算子

メンバ関数

{
  int A[10] = {5,2,8,9,1,1,100,800,9,10};
  int B[10];
  int sz;
  int pp1[10] = {1,2,3,4,5,6,7,8,9,0};
  int pp2[10] = {1,0,3,2,5,4,7,6,9,8};

  Permutation p1, p2, m, id;
  p1.changeSize(10);
  p2.changeSize(10);
  rep(i,10) p1[i] = pp1[i];
  rep(i,10) p2[i] = pp2[i];



  wt(A(10));           // 5 2 8 9 1 1 100 800 9 10
  p1.apply(A, B);
  wt(B(10));           // 10 5 2 8 9 1 1 100 800 9
  p2.apply(A, B);
  wt(B(10));           // 2 5 9 8 1 1 800 100 10 9



  m = p1 ** 13;
  m.apply(A, B);
  wt(B(10));           // 800 9 10 5 2 8 9 1 1 100



  m = p1 * p2;
  m.apply(A, B);
  wt(B(10));           // 9 2 5 9 8 1 1 800 100 10

  p2.apply(A);
  p1.apply(A);
  wt(A(10));           // 9 2 5 9 8 1 1 800 100 10


  id.changeSize(10);
  id = 1;              // identity
  rep(i,100){
    m = p1 ** i;
    if(m==id) wt(i);   // i = 0, 10, 20, ..., 90
  }
  rep(i,100){
    m = p1 ** i;
    if(m==p1) wt(i);   // i = 1, 11, 21, ..., 91
  }


  sz = p1.cycle_len(B);
  wt(B(sz));              // 10
  sz = p2.cycle_len(B);
  wt(B(sz));              // 2 2 2 2 2
  sz = id.cycle_len(B);
  wt(B(sz));              // 1 1 1 1 1 1 1 1 1 1
}

IntMap

{0,1,...,n-1} から {0,1,...,n-1} の写像は IntMap f; などで定義します．
f[i] = j は第i要素を第j番目に飛ばす，という意味です．

コンストラクタ

デストラクタ

演算子

メンバ関数

変数

変数（多分使わない）

Fenwick Tree (Binary Indexed Tree, BIT)

（1次元の）Fenwick treeが使えます．
fenwick<int> t; などで定義します．この場合は各要素や和などを求める時に全てint型で計算されます．
扱う配列の長さの最大値を maxN として，t.malloc(maxN); または t.walloc(maxN); でメモリを確保します．
その後，配列の長さが N の場合に初期化（全要素を0にする）場合，t.init(N); とします．
メモリ確保とともに，確保したメモリ分の長さを初期化する場合は，t.malloc(N, 1); または t.walloc(N, 1); です．

関数などは以下の通り（fenwick<T> t; で宣言したとします．また，要素数を $N$ として，0番目の要素から$N$-1番目の要素まで存在します）：

区間は閉区間 [a,b] の形で指定することに注意して下さい．

malloc()を使った場合のメモリの開放は t.free(); です．

  {
    int d[10] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 4};
    int arr[20];
    int i, s;

    fenwick<int> t;
    t.walloc(10);
    t.init(10);
    rep(i,10) t.add(i,d[i]);

    s = t.get(3);
    wt(s); // d[0]+d[1]+d[2]+d[3] = 3+1+4+1 = 9
    s = t.range(5,7);
    wt(s); // d[5]+d[6]+d[7] = 9+2+6 = 17

    rep(i,20) arr[i] = t.kth(i);
    wt(arr(20)); // 0がd[0]個，1がd[1]個，…からなる配列のk番目の要素
                 // 0 0 0 1 2 2 2 2 3 4 4 4 4 4 5 5 5 5 5 5
  }

バイナリヒープ（priority_queueとほぼ同様）

Heap<T> h; もしくは Heap_max<T> hm; で宣言する．
Heapは通常の最小値を取り出せるやつ，Heap_maxは最大値を取り出せるやつ．
大体の操作は $O(\log size)$．

Heap<T> h; について：

Heap_max<T> hm; について：

バイナリヒープ（固定長配列用）

LHeap<int> などで宣言．
$N$ 要素の配列 $A_k = \verb|val[k]|$ を考える．
ヒープにある要素を入れたり値を変えたり（$\verb|change|$），ヒープの中に入っている最小の要素を取り出して取り出した要素の番号を返したり（$\verb|pop|$）する．
大体の操作の計算時間 $O(\log N)$．

よく使いそうなもの：

そうではないもの：

  int i;
  double v;
  LHeap<double> hp;

  hp.walloc(10);
  hp.init(10);

  hp.change(0, 100.0);
  hp.change(1, 200.0);
  hp.change(8, 80.0);
  hp.change(1, -200.0);
  hp.change(8, 150.0);

  while(hp.size){
    i = hp.pop();   // 1 -200.000000000000000
    v = hp.val[i];  // 0 100.000000000000000
    wt(i,v);        // 8 150.000000000000000
  }

バイナリヒープ（ダイクストラ用）

DijkstraHeap<int> などで宣言．
バイナリヒープ（固定長配列用）のダイクストラ用にチューニングしたもの．
$\verb|pop|$ した時に $\verb|visited[]|$ のフラグを立てる，更新時に訪れたものや長くなったものは更新しないなどを関数の中で判定する．

よく使いそうなもの：

そうではないもの：

  int i;
  double v;
  DijkstraHeap<double> hp;

  hp.walloc(10);
  hp.init(10);

  hp.change(0, 100.0);
  hp.change(1, 200.0);
  hp.change(8, 80.0);
  hp.change(1, -200.0);
  hp.change(8, 150.0);

  while(hp.size){
    i = hp.pop();   // 1 -200.000000000000000
    v = hp.val[i];  // 8 80.000000000000000
    wt(i,v);        // 0 100.000000000000000
  }

セグメントツリー（標準的なの？）

（1次元の）セグメントツリーが使えます．
segtree<int> t; などで定義します．この場合は各要素や和などを求める時に全てint型で計算されます．
1回のみ使用する場合は，配列の長さを N として t.malloc(N, 1); とすると，配列の要素が全て 0 で初期化され，セグメントツリーが使えるようになります．
何回も使いまわす可能性がある場合は，配列の長さの最大値を maxN として，t.malloc(maxN); でメモリを確保します．
その後，配列の長さが N の場合にセグメントツリーを使えるようにするためには，t.setN(N); で使えるようになります．
mallocの代わりにwallocでワーキングメモリを使ってメモリを確保します．

0以外で初期化したい場合は，t.setN(N,0,0);（各要素は全く初期化されない），または，t.setN(N,1,0); （各要素は一応0で初期化される）としておき，
t[hoge] = 要素hogeの初期値;
と適当に初期化した後，t.build();とすれば使えるようになります．

segtree<T> t; とした場合，使える感じの関数は以下の通り（要素数を $N$ として，0番目の要素から$N$-1番目の要素まで存在します）：

区間は最初は含むが最後は含まない [a,b) の形で指定することに注意して下さい．

malloc()を使った場合のメモリの開放は t.free(); です．

セグメントツリー（亜種？）

初期化の仕方などは標準的な segtree と同じですが，機能が制限されていたり，変な機能がついているものです．
基本的に必要な機能のみがついているものを使うと，速くて省メモリのはずです．
基本的に構造体の名前が segtree_[変更に対する対応クエリの羅列]_[取得に関する対応クエリの羅列] という形式になっています（長い…）．
例えば，
segtree_Point_SumMin<T> t;
だと，変更に関するクエリの
void t.add(int x, T val)
void t.change(int x, T val)
と取得に関するクエリの
T t.getSum(int a, int b)
pair<T, int> t.getMin(int a, int b)
T t.getMinVal(int a, int b)
int t.getMinInd(int a, int b)
が使用できます．

変更に関するクエリと構造体の名前に含まれていたら使用できるという文字列（,で区切られている場合どれかが含まれていれば使用可能）

取得に関するクエリと構造体の名前に含まれていたら使用できるという文字列（,で区切られている場合どれかが含まれていれば使用可能）

定義されている構造体

その他の事項：
segtree_ChangeAdd_SumMin は通常の segtree を使ってください．
segtree_Point_Sum（1点更新で和を求めるだけのもの）はfenwickでできます（が，t.change(int x, T val) に対応するには値を配列などに保持し，差分を足してください）．

セグメントツリー（1点更新の汎用的なの）

segtree_ph<T> t; で定義します．
初期化は通常のsegtreeと同じですが，0で初期化するように指定しても初期化されません（同じように書けるように引数は存在します）．

res = f(a, b) を計算する関数
T segtree_ph_func(T a, T b){ hoge; }
をグローバルで定義しておきます．fは結合律 f(a,f(b,c)) = f(f(a,b),c) =: f(a,b,c) を満たすとします．

例えば，T = int で，
void segtree_ph_func(int a, int b){ return a + b; }
を作っておくと，1点更新で，区間和を求めることができるsegtreeになります．

ただし，基本的には，汎用的に利用するため，構造体と関数を新しく定義して利用することを想定しています．
実装方法は以下も参考にしてください．
Codeforces Round #672 DIV2 C2問題 - Pokemon Army (hard version)

セグメントツリー（1点更新の汎用的なの，旧版）

segtree_phとの違いは segtree_p*_func の形式です．

segtree_pg<T> t; で定義します．
初期化は通常のsegtreeと同じですが，0で初期化するように指定しても初期化されません（同じように書けるように引数は存在します）．

res = f(a, b) を計算する関数
void segtree_pg_func(T &res, T &a, T &b){ hoge; }
をグローバルで定義しておきます．fは結合律 f(a,f(b,c)) = f(f(a,b),c) =: f(a,b,c) を満たすとします．

例えば，T = int で，
void segtree_pg_func(int &res, int a, int b){ res = a + b; }
を作っておくと，1点更新で，区間和を求めることができるsegtreeになります．

ただし，基本的には，汎用的に利用するため，構造体と関数を新しく定義して利用することを想定しています．
実装方法は以下も参考にしてください．
Codeforces Round #672 DIV2 C2問題 - Pokemon Army (hard version)

segtree_pg 名前の由来は p は1点更新を意味する point，g はグローバルに関数を定義する形式から名前をつけています．

セグメントツリー（区間更新の汎用的なの）

segtree_rh<SVAL, SFUN> t; で定義します．
初期化は通常のsegtreeと同じですが，0で初期化するように指定しても初期化されません（同じように書けるように引数は存在します）．

res = h(a, b) を計算する関数
SVAL segtree_rh_merge(SVAL a, SVAL b){ hoge; }
をグローバルで定義しておきます．hは結合律 h(a,h(b,c)) = h(h(a,b),c) =: h(a,b,c) を満たすとします．

変更に関して，res = f(a) を計算する関数
SVAL segtree_rh_apply(SFUN f, SVAL a){ hoge; }
および，関数の合成 res(x) = f(g(x)) なる関数 res を計算する関数
SFUN segtree_rh_compose(SFUN &res, SFUN f, SFUN g){ hoge; }
をグローバルで定義しておきます．

AtCoder Libraryのlazy_segtreeとだいたい同じ機能です．実装方法は例えば以下を参考にしてください．
AtCoder Library Practice Contest K問題 - Range Affine Range Sum
AtCoder Library Practice Contest L問題 - Lazy Segment Tree

また，changeでは全て一定値で置き換え，getで最小値を取得の場合は，segtree_rh<ll, ll> で，
ll segtree_rh_apply(ll f, ll a){ return f; }
ll segtree_rh_merge(ll a, ll b){ return min(a, b); }
ll segtree_rh_compose(ll f, ll g){ return f; }
などでできますが，複雑になると構造体を作ったほうがわかりやすい気がします．

セグメントツリー（区間更新の汎用的なの，旧版）

segtree_rh との違いは segtree_rg_func の関数名，関数の形式の違いと，恒等写像を用意する必要があるところです．

segtree_rg<SVAL, SFUN> t; で定義します．
初期化は通常のsegtreeと同じですが，0で初期化するように指定しても初期化されません（同じように書けるように引数は存在します）．

res = h(a, b) を計算する関数
void segtree_rg_func(SVAL &res, SVAL a, SVAL b){ hoge; }
をグローバルで定義しておきます．hは結合律 h(a,h(b,c)) = h(h(a,b),c) =: h(a,b,c) を満たすとします．

変更に関して，res = f(a) を計算する関数
void segtree_rg_func(SVAL &res, SFUN f, SVAL a){ hoge; }
および，関数の合成 res(x) = f(g(x)) なる関数 res を計算する関数
void segtree_rg_func(SFUN &res, SFUN f, SFUN g){ hoge; }
をグローバルで定義しておきます．
また，恒等写像を表す写像 res を返す
void segtree_rg_id(SFUN &res)
もグローバルで定義しておきます．

SVAL, SFUN を同じ型にすることは現状できません．
基本的には，汎用的に利用するため，構造体と関数を新しく定義して利用することを想定しています．

AtCoder Libraryのlazy_segtreeとだいたい同じ機能です．実装方法は例えば以下を参考にしてください．
AtCoder Library Practice Contest K問題 - Range Affine Range Sum
AtCoder Library Practice Contest L問題 - Lazy Segment Tree

また，changeでは全て一定値で置き換え，getで最小値を取得の場合は，segtree_rg<int, ll> で，
void segtree_rg_id(ll &res){ res = ll_inf; }
void segtree_rg_func(int &res, ll f, int a){ res = if[f==ll_inf, a, f]; }
void segtree_rg_func(int &res, int a, int b){ res = min(a, b); }
void segtree_rg_func(ll &res, ll f, ll g){ res = if[f==ll_inf, g, f]; }
などでできますが，構造体を作る余裕があるなら作ったほうがわかりやすい気がします．

segtree_rg 名前の由来は r は区間更新を意味する range，g はグローバルに関数を定義する形式から名前をつけています．

2次元領域木，2d range tree

2次元平面内の長方形領域に含まれる点の重みの和を求める．
rangeTree2d<S,T1,T2> t; で定義する．
Sは重みの型，T1は1次元目（x座標）の型，T2は2次元目（y座標）の型．
実装は現状，y座標の区間を扱うようなsegment treeで，各ノードには対応するx座標値をソートして保持，x座標の区間の重みを計算できるようにFenwick treeを保持．
領域量は O(N log N) でワーキングメモリを結構使うので注意．必要ならば，//working_memory=300m などしておくと良い．

重みが一様（全て1）のバージョン rangeTree2d_nw もあります．nwはnon-weightedのつもり．
rangeTree2d<T1,T2> t; で定義する．

グラフ（構造体）

graph構造体を使えます．graph g; などで定義します．

{
  int N = 6, M = 7;                       //  0 → 1 ← 2
  int A[7] = {0, 0, 1, 2, 3, 4, 5};       //  |    ^    |
  int B[7] = {1, 3, 2, 5, 4, 1, 4};       //  v    |    v
                                          //  3 → 4 ← 5
  int i;
  graph g;
  int dist[6];

  g.setEdge(N, M, A, B);                  // node 0: degree 2: 1 3
  rep(i,N){                               // node 1: degree 3: 0 2 4
    wtF("node {i}: degree {g.es[i]}: ");  // node 2: degree 2: 1 5
    wt(g.edge[i](g.es[i]));               // node 3: degree 2: 0 4
  }                                       // node 4: degree 3: 3 1 5
                                          // node 5: degree 2: 2 4
  g.getDist(3, dist);
  wt(dist(N));            // 1 2 3 0 1 2

  g.setDirectEdge(N, M, A, B);            // node 0: degree 2: 1 3
  rep(i,N){                               // node 1: degree 1: 2
    wtF("node {i}: degree {g.es[i]}: ");  // node 2: degree 1: 5
    wt(g.edge[i](g.es[i]));               // node 3: degree 1: 4
  }                                       // node 4: degree 1: 1
                                          // node 5: degree 1: 4
  g.getDist(3, dist);
  wt(dist(N));            // -1 2 3 0 1 4
}

枝に重みのあるグラフ（構造体）

wgraph構造体を使えます．wgraph<T> g; などで定義します．

Heavy-Light Decomposition（HLD，重軽分解）

根付き無向木に対してHeavy-Light Decomposition（HLD）を計算します．
根はノード0を利用します．
計算したHLDを用いて，LCAなどを高速に求めることができます．
また，segtreeを載せることができます．
HLD hld; で定義したとします．

以下 HLD hld; の多分使わない情報．

Fenwick treeを載せるときは，HLD_fenwick<T> t; を定義します．
ノードに値を持ちます．
（枝に値をもたせたい場合は，すぐ上に向かう枝の値をノードに持たせて，LCAでパスを分割したりするとできるかも）

以下 HLD_fenwick<T> t; の多分使わない情報．

segtreeを載せるときは，HLD_segtree<T> t; を定義します．
ノードに値を持ちます．

枝に重みが載っていると思った場合の関数は以下の通り（実際は枝(x,y)の重みはx,yの内，深い方のノードに持たせていて，内部でLCAやら色々呼び出して辻褄合わせたりするので多分遅め）

以下 HLD_segtree<T> t; の多分使わない情報．

最大流（maxflow, Dinic）

最大流は maxflow<int,ll> flow; などで定義します．この場合，各辺の流量は int 型ですが，合計で流れる流量は ll 型です．
以下の説明では maxflow<T,S> flow; とします．

以下のコードは http://www.spoj.com/problems/FASTFLOW/ を解くコード．

int A[30000], B[30000], C[30000];
{
  int N, M;
  ll res;
  maxflow<int,ll> f;

  rd(N,M);
  rd((A,B,C)(M));
  A[0..M-1]--;
  B[0..M-1]--;

  f.malloc(N);
  f.init(N);
  f.addEdge(A[0..M-1],B[0..],C[0..],C[0..]);
  res = f.solve(0, N-1);
  wt(res);
}

最小費用流（minCostFlow）

最大流は minCostFlow<int,double> flow; などで定義します．この場合，流量は int 型で，コストは double 型です．
以下の説明では minCostFlow<FT,CT> flow; とします．
徐々に流していくアルゴリズムを適当に実装したもので，少なくても現状は良い実装ではないと思います．
負の閉路などがあると動きません．

参考：yukicoder No.1288 - yuki collection

Trie

Trie t; で定義したとします．
最終的なノード数の上限を n（例えば食わせる文字列の文字数の和+1），アルファベットのサイズ（文字の種類数）を k として，t.malloc(n, k); などでメモリの確保 + 初期化します．
n=10^6, k=26 で100メガバイト以上メモリが必要なので注意してください（nk*sizeof(int)は最低限必要で，それ以外も細々と必要かも）．
ルート（空文字）に対応するノード番号は 0 です．

AhoCorasick

AhoCorasick aho; で定義したとします．
最終的なノード数の上限を n（例えば食わせる文字列の文字数の和+1），アルファベットのサイズ（文字の種類数）を k として，aho.malloc(n, k); でメモリの確保＋初期化します．
アルファベットは0からk-1までの数値です．
文字列を addWord でいくつか加えてTrieぽいグラフを作る．
そして，construct で failedリンクを作って準備完了です．

全ての文字列を区別する必要がなければ以下のもので十分かもしれません．

AhoCorasick_Sum<S> aho; で定義したとします．
最終的なノード数の上限を n（例えば食わせる文字列の文字数の和+1），アルファベットのサイズ（文字の種類数）を k として，aho.malloc(n, k); でメモリの確保＋初期化します．
アルファベットは0からk-1までの数値です．
文字列を addWord でいくつか加えてTrieぽいグラフを作る．
そして，construct で failedリンクを作って準備完了です．

AhoCorasickの使い方の参考：
AtCoder Beginner Contest #122 D問題 - We Like AGC

Polynomial（1変数多項式）

あまりちゃんと作っていません．
Polynomial<T> P; で作ります．定義域，値域ともにTです．
疎構造ではないので，次数の高い多項式は問答無用でたくさんの項を扱うことになって遅いです．
今のところ愚直な実装です．

コンストラクタ

デストラクタ

その他関数 [メンバ関数]

オペレーター [メンバ関数]

オペレーター [メンバ関数以外]

使わなさそうなの

  double x;
  Polynomial<double> P, Q, R1, R2; // P = Q = 0

  P.change(2, 1); // P = x^2
  P.change(1, 2); // P = x^2 + 2*x
  P.change(0, 1); // P = x^2 + 2*x + 1

  x = P(2); // P(2) = 2^2 + 2*2 + 1 = 9

  Q.change(1, 1); // Q = x
  Q.change(0, 4); // Q = x + 4

  // x^2 + 2*x + 1 = (x-2) (x+4) + 9
  R1 = P / Q;  // x - 2
  R2 = P % Q;  // 9

  Q *= 2.0; // 2x + 8

  // x^2 + 2x + 1 = (0.5x - 1) (2x + 8) + 9
  R1 = P / Q; // 0.5x - 1
  R2 = P % Q; // 9

  Q.change(1, 0); // Q = 8
  R1 = P / Q; // (1/8) x^2 + (1/4) x + (1/8);
  R2 = P % Q; // 0

その他色々な関数など

  int i, j;
  int *a, **m, **hoge;

  walloc1d(&a, 100);
  walloc2d(&m, 50, 100);

  rep(i,100) a[i] = i;
  rep(i,50) rep(j,100) m[i][j] = i+j;
                                 // ↓出力 *例* (sizeof(*a)=4の環境)
  printf("%p %d\n",a,a);         // 0x404040 4210752
  printf("%p %d\n",m,m);         // 0x4041d0 4211152
  printf("%p %d\n",m[0],m[0]);   // 0x404298 4211352
  printf("%p %d\n",m[1],m[1]);   // 0x404428 4211752

  malloc2d(&hoge, 50, 100);
  free2d(hoge);

  int *a;
  void *mem;

  mem = wmem;        // ワーキングメモリの先頭アドレスを覚えておく
  walloc1d(&a, 1d6); // 10^6要素の配列を確保
  /* 何かする */
  wmem = mem;        // ワーキングメモリの先頭アドレスを戻すことによって，配列aを解放

Rand構造体．乱数生成に使う．xorshift．
Rand rnd; で宣言したとして以下の通り．
何回か実行したとき，うまく種を設定しないと最初の数十回ぐらいは似た系列が出てくるので，気になる場合は，最初にgetを100回呼び出すなど空打ちすると良い．
一部仕様は未決定．
種を設定しない場合は，time(NULL)を使って設定．

以下は微妙に仕様を決めきれてない．

以下はそのうち実装予定でまだ作ってない

unionfind構造体．unionFind uf; で宣言したとして以下の通り．

以下あまり使わないやつ

rollbackUnionfind構造体．rollbackUnionFind uf; で宣言したとして以下の通り．
ただし，unionFindで使えるものは全てそのまま使える．
経路圧縮をしないので，一部の計算量はアッカーマン逆関数からlogになっている．

Timer構造体．時間を測るために使う．Timer timer;で宣言したとして以下の通り．gettimeofdayを使用する．

  int i;
  ll sum = 0;
  Timer timer;
  double tm;
  timer.set();
  rep(i,1,1d8) sum += 1d9 /+ i;
  tm = timer.get();
  wtF("time: {tm}, sum: {sum}\n"); // time: 0.678610086441040, sum: 19048729277

  int i;                               // (1,2)      ←出力結果
  int A[5] = {3,1,3,5,2};              // (2,5)
  int B[5] = {1,2,3,4,5};              // (3,1)
  sortA(5,A,B);                        // (3,3)
  rep(i,5) wtF("({A[i]},{B[i]})\n");   // (5,4)

x if[c1,s1,c2,s2,e] y; は if(c1){ x s1 y; } else if(c2){ x s2 y; } else { x e y; } に展開される．(c1,s1)のペアはいくつ合っても良い．eは空なら省略可能．
ただし，現状if文などの()の中では使用不可能．
例えば

  a[i] = x if[i%2==0,+,-] y;
  s[i] = b[i] if[i,+s[i-1]];

は以下のように展開されます：

  if(i%2==0){
    a[i] = x + y;
  } else {
    a[i] = x - y;
  }
  if(i){
    s[i] = b[i] + s[i-1];
  } else {
    s[i] = b[i];
  }

式に対して最小値，最大値，和などを求める．
最小値の場合は，
min[型][範囲](式)
の形式で [型] は省略可能（int型をたくさん足してll型で結果を得たい場合などは [型] を指定する）．
範囲を表す変数は int 型ですが，他の型の場合は範囲の書き方を見てください．
範囲が空なら，sumは0，mulは1，gcdは0，lcmは1になります．minは型が表せる最大の値，maxは型が表せる最小の値になります．

範囲の書き方は以下のとおりです．
各変数の動く範囲を,区切りで記述します（変数は定義されていなくても構いません，式の評価にのみ利用します）．
i=a---b : 変数 i を a から b まで（両端を含む）動かします．
i,a,b : 変数 i を a から b-1 まで（両端を含む）動かします．
(i,j)=a---b : 変数 i と j を a から b まで（両端含む）動かします．
(i,j),a,b : 変数 i と j を a から b まで（両端含む）動かします．

変数の型を指定する場合は，変数名の前につけてください．
例えば (i,j),a,b において i は int 型だけど，j を ll 型にする場合は (i, ll j),a,b としてください．

また，配列に対する argmin, argmax は以下の形式も使えます．

  {
    int i;
    i = min[k=1---100](abs(4*k-50));
    wt(i);                               // 2 と表示
    i = argmin[k=1---100](abs(4*k-50));
    wt(i);                               // 12 と表示
  }
  {
    int A[3][3] = {
      300000000, 500000000, 700000000,
      300000000, 200000000, 700000000,
      300000000, 500000000, 900000000
    };
    wt(min[i,0,3,j,0,3](A[i][j]) + max[i,0,3,j,0,3](A[i][j])); // 1100000000 = 200000000 + 900000000
    wt(sum[ll][i,0,3,j=0---2](A[i][j])); // 4400000000 (ll型なのでオーバーフローしない)
    wt(gcd[(i,j),0,3](A[i][j])); // 100000000
    wt(lcm[ll][(i,j),0,3](A[i][j])); // 63000000000
  }
  {
    wt(max[ll i,1d10,1d10+20](i+2)); // 10000000021
  }

それぞれ単調性が成り立たなければならない．
例えば，bsearch_minの場合，name=10のときcondが成り立つならば，name=10以上（maxval以下）のときもcondは成り立たなければならない．
typeは変数nameの型を指定し，float, doubleの場合は実数の二分探索，それ以外は整数の二分探索を行う．
bsearch_minでは，name=maxvalでは評価されず，name=maxvalより小さい場合に常に偽ならmaxvalが返ってくる（name=maxvalのときはblock, condが未定義になるようなものでも良い）．
今のところ，minval, maxvalは省略不可能．

optionは以下の通り．

実数の二分探索で，許容誤差を指定しない場合は，見ている範囲を[x,y]としたとき，(x+y)/2が（計算機上で）xまたはyに一致したら打ち切る（許容誤差を指定してもこの判定は行う）．

  int i, j, k, t;
  double x, y;

  k = -1;
  i = bsearch_max[int,k,0,100](k*k<=10);
  j = bsearch_min[int,k,0,100][
    t = 0;
    rep(j,1,k+1) t += k / j;
  ](t >= 100);
  x = bsearch_max[double,x,0,100](x*x<=10);
  y = bsearch_max[double,x,0,100,E=1e-1](x*x<=10);

  wt(i,j,k,x,y); // 3 28 -1 3.162277660168380 3.222656250000000

三分探索（内部実装は少し違うかも）のようなもの．二分探索とほぼ同様の書き方．

optionは以下の通り．

最小値を求める場合，name=kのときのeqの値を f(k) と書くことにしたら，とある L ≤ R が存在して
minval ≤ x < y ≤ L のとき f(x) > f(y),
L ≤ x < y ≤ R のとき f(x) = f(y),
R ≤ x < y ≤ maxval のとき f(x) < f(y)
が成り立たなければならない．

{
  wt(tsearch_min[ll,x,-1d9,1d9](x*(x+10)));                                 // -25
  wt(tsearch_argmin[ll,x,-1d9,1d9](x*(x+10)));                              // -5

  wt(tsearch_max[ll,x,-1d9,1d9,T=ll][ll y; y = x + 5;](-(y-5)*(y+5)));      // 25
  wt(tsearch_argmax[ll,x,-1d9,1d9,T=ll][ll y; y = x + 5;](-(y-5)*(y+5)));   // -5
}

参考：Codeforces Round #679 DIV1 C問題 - Solo mid Oracle

  int fac[100], fs[100], fsz;
  int dv[100], dsz;

  fsz = Factor(1500, fac, fs);   // 1500 = 2^2 * 3^1 * 5^3
  rep(i,fsz) wt(fac[i], fs[i]);  // fsz=3, fac={2,3,5}, fs={2,1,3}

  fsz = Factor(1500, fac);
  wt(fac(fsz));                  // 2 3 5

  fsz = FactorM(1500, fac);
  wt(fac(fsz));                  // 2 2 3 5 5 5

  dsz = Divisor(24, dv);
  wt(dv(dsz));                   // 1 2 3 4 6 8 12 24

関数名がよく使う名前なのでこの機能を無効化するフラグがあります（フラグの欄を参照のこと）．
引数の型は違っても構いませんが，計算途中でどのような型になるかは不明です（オーバーフローなどに注意）．
今のところ，整数と浮動小数点数ぐらいでしか上手く動かないと思います．例外的にsum()はstring型でも動くはずです（文字列を連結します）．
配列は長さ0の配列を与えると上手く動かないことがあります．

  int i = 10, j = 75;
  int k[3] = {100, 200, 300};
  wt(gcd(i,j,k(3))); // gcd(10,75,100,200,300) = 5
  wt(min(i,j,k(3))); // min(10,75,100,200,300) = 10
  wt(sum(i,j,k(3))); // sum(10,75,100,200,300) = 685

Comb 構造体は（1つ下のconbination_mintのように）階乗などを前計算しておき組合せ的な数を求める構造体です．
Comb<T> comb; で定義したとします．T は mint, modint, Mint, Modint のどれかを想定しています．
必要な値がない場合は，必要になったときに勝手に計算します．

使いそうなの

使わなさそうなの：変数

使わなさそうなの：関数

combination_mint は階乗とその逆数を前計算することで二項係数を高速に求めます．mint型で答えを返します．
構造体を使用しているので combination_mint comb; と最初に宣言して下さい．

  combination_mint comb;
  mint res;

  comb.init(101);     // 100の階乗までを計算．以降 C(100,hoge) まで計算可能
  res = comb.C(5,2);
  wt(res);            // 10 = 5*4/2 = 5個から2個を選ぶ選び方

  int a = 32, b = 24;
  reduceFraction(a,b);
  wtF("{a}/{b}\n");         // 4/3 と表示

  int i, f[10];
  rep(i,10) f[i] = fib_mod(i);
  wt(f(10));                    // 0 1 1 2 3 5 8 13 21 34

  int n;
  int C[5] = {1000, 100, 1, 8, 100};
  
  n = coordcomp(4, C);
  wt(n);       // 4
  wt(C(5));    // 3 2 0 1 2
  
  int A[5] = {100, 4, 8, 4, 100};
  int B[4] = {8, 2, 1200, 8};
  int rA[5], rB[4];

  n = coordcomp(5, A, 4, B, rA, rB);
  wt(n);       // 5
  wt(A(5));    // 100 4 8 4 100
  wt(B(4));    // 8 2 1200 8
  wt(rA(5));   // 3 1 2 1 3
  wt(rB(4));   // 2 0 4 2

次元圧縮．多次元のグリッドでのBFSなどに．
構造体で，[x]次元のものは dimcomp[x] c; で定義したとする．2次元～5次元まで．

2次元 dimcomp2 c; で定義．

3次元 dimcomp3 c; で定義．

4次元 dimcomp4 c; で定義．

5次元 dimcomp5 c; で定義．

  int dx, dy, mask;
  dimcomp2 c(20,15);    // size = 20 x 15 (dimcomp2 c(15) でもほぼ同じ)
  dx = 3; dy = 9;
  mask = c(dx,dy);
  wt(mask);             // 3 * 15 + 9 = 54
  mask = c(dx+1, dy);
  wt(mask);             // 4 * 15 + 9 = 69
  c(mask,dx,dy);
  wt(dx,dy);            // dx = 4, dy = 9

  {
    int N = 7;
    int A[7] = {7,4,1,4,1,4,1};
    Unique(N,A);
    // N = 3, A = {1, 4, 7}
  }
  {
    int N = 7;
    int A[7] = {7,4,1,4,1,4,1};
    int B[7] = {1,2,2,2,2,2,2};
    Unique(N,A,B);
    // N = 3
    // A = {1, 4, 7}
    // B = {6, 6, 1}
  }

twoMultisets構造体．
格納するデータの型をTとして twoMultisets<T> s; で定義します．格納している要素数を N と書くことにします．
中身は2つのmultisetからなっていて，小さい方のいくつかと大きい方のいくつかを格納しています．
K番目の値を知りたい場合は，小さい方K個と大きい方N-K個を格納するようにする，などと適当に要素を移動させてクエリに答えます．
Kが固定，Kが常にN/2，Kが単調に動く，などの場合に効率的にクエリに答えることができると予想されます．
和を求めることもできますが，和も T 型で格納できる必要があります．
名前の由来は twopointers っぽい動き方しているような気がしたから．

使わないもの

  {
    int d[10] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 4};
    int inv;
    inv = inversion_range(10, d, 1, 9);
    wt(inv); // 14
  }
  {
    double d[10] = {1e3, 1e1, 1e4, 1e1, 1e5, 1e9, 1e2, 1e6, 1e5, 1e4};
    int inv;
    inv = inversion(10, d);
    wt(inv); // 14
  }

非負整数 x, y を2進数で書いたとき，xの1の桁がyの1の桁に包含されているとき，xはyに含まれると呼ぶことにする．
ZetaTransform は res[i] は jがiに包含されている整数を動くとき A[j] の和が代入されます．
メビウス変換はゼータ変換の逆変換です．

  int A[6] = {2,5,9,4,1,8}, B[6], C[6];
  ZetaTransform(6, A, B);
  MoebiusTransform(6, B, C);
  rep(i,6) printf("%d %d%d%d %02d %02d %02d\n", i, (i>>2)%2, (i>>1)%2, i%2, A[i], B[i], C[i]);
// 0 000 02 02 02
// 1 001 05 07 05
// 2 010 09 11 09
// 3 011 04 20 04
// 4 100 01 03 01
// 5 101 08 16 08

res[i] は jがiに包含されている整数を動くとき A[j] の最小値 | 最大値を求めるのは以下の関数です．
小さい方から2個，3個求めるものもあります．この場合は，要素数が足りない場合は，numeric_limits<S>::max();が代入されます．

  int N = 10;
  int A[10] = {0,0,1,1,1,0,0,3,2,1};  // 0が2個 - 1が3個 - 0が2個 - 3が1個 - 2が1個 - 1が1個
  int e, val[10], len[10];

  e = runLength(N,A,val,len);
  wt(e);                         // 6 と表示されます
  wt(val(e));                    // 0 1 0 3 2 1
  wt(len(e));                    // 2 3 2 1 1 1

いずれの関数も，空のmultiset, setを引数に取ってはいけません．

基本的にグレゴリオ暦を仮定

  int A[10] = {1,2,3,1,2,3,1,2,3,1};
  int B[4] = {1,2,3,1};
  int res[10], cnt;

  cnt = KMP(A, 10, B, 4, res);
  wt(cnt);      // 3
  wt(res(10));  // 1 0 0 1 0 0 1 0 0 0

  char S[12] = "abracadabra";
  int SA[12], LCP[12];
  SuffixArray(S, 11, 128, SA, LCP);
  rep(i,12) printf("%4d %4d %4d %s\n", i, SA[i], LCP[i], S+SA[i]);
  /*
   0   11   -1
   1   10    0 a
   2    7    1 abra
   3    0    4 abracadabra
   4    3    1 acadabra
   5    5    1 adabra
   6    8    0 bra
   7    1    3 bracadabra
   8    4    0 cadabra
   9    6    0 dabra
  10    9    0 ra
  11    2    2 racadabra
  */

Arr1d 構造体．
累積和を計算しておけば連続する部分列の和を計算できたりするような，1回準備したら（配列の中身を変更しなければ）簡単に答えられるようなクエリに対応するための型です．
（計算状況リセットしてから）最初の1回のみ，連続部分列の和を取得しようとしたときに累積和を計算するような感じ．
以下は，Arr1d<T> a;を想定．

[特殊な話]
int n; Arr1d<ll> a;
rd(n, a(n));
と読み込むことができます．
rd(a(n));で読み込んだときには，読み込む直前に a.malloc(n); が走って勝手にメモリ確保と配列サイズが指定されます．
a[0], a[1], ..., a[n-1] で普通に要素にアクセスできます．

[コンストラクタ・メモリ関係・初期化など]

[累積和関係]

[縦横に連続する数]

[ヒストグラム（密な場合）]

[その他]

[基本的に使わない情報]

Grid1d構造体．
Grid1d<int> g; などで定義し，g.malloc(n); でメモリを確保する．メモリ解放するときは g.free(); ．
すると，g[i]が使えるようになり，それぞれint型．
g[i] にデータを代入して，g.setSum()，g.setDir() 等で累積和などのテーブルを作成して，利用する．
データを変更した場合は，g.setSum() などを再度呼び出せば良い．
行の数，列の数を変更する場合は，現状，g.free()→g.malloc(n)とやり直すしかない．
以下は，Grid1d<T> g;を想定．

累積和関係

縦横に連続する数

Grid2d構造体．
Grid2d<int> g; などで定義し，g.malloc(r,c); でメモリを確保する．メモリ解放するときは g.free(); ．
すると，g[i][j]が使えるようになり，それぞれint型．
g[i][j] にデータを代入して，g.setSum()，g.setDir() 等で累積和などのテーブルを作成して，利用する．
データを変更した場合は，g.setSum() などを再度呼び出せば良い．
行の数，列の数を変更する場合は，現状，g.free()→g.malloc(r,c)とやり直すしかない．
以下は，Grid2d<T> g;を想定．

累積和関係

縦横に連続する数

その他

ビットに関すること．

FFTを用いて畳み込みを行います．
誤差がそれなりにのるので使用する際には注意．

FFTを用いて畳み込みを行います．
mod の値は 2冪+1 でなければならないなどの条件が存在します．
root には mod の原始根のうちの1つを指定してください．defineしたMDが素数の場合，その原始根は MD_PRIMITIVE_ROOT で勝手にdefineされます．

  double a[3] = {1,2,3}, b[3] = {1,2,3}, c[6];
  convolution(a, 3, b, 3, c, 6);
  wt(c(6));  // 0.999999999999999 3.999999999999999 10.000000000000000 12.000000000000000 9.000000000000000 0.000000000000001
  convolution(a, 3, c, 6);
  wt(c(6));  // 0.999999999999999 3.999999999999999 10.000000000000000 12.000000000000000 9.000000000000000 0.000000000000001

グラフの隣接リスト（隣接配列？）のようなものを作ります．
時間ごとにイベントを処理する場合などの整理などにも多分便利．

    int A[5] = {1,1,3,3,0}, B[5] = {10,30,30,30,50};
    int *es, **edge;
    wAdjEdge(4, 5, A, B, &es, &edge);
    rep(i,4) wt(i, ':', es[i], ':', edge[i](es[i]));
//  0 : 1 : 50
//  1 : 2 : 10 30
//  2 : 0 :
//  3 : 2 : 30 30

ハンガリアン法．n ≤ m と仮定．
mat[0][c[0]] + mat[1][c[1]] + ... + mat[n-1][c[n-1]] の最小値を求める．ただし，c[i]は互いに異なる（c[i]は0以上m未満）．
それを達成する配列cはmatch[]に代入して返す．matchにNULLにしておくと最小値だけ返す．

多項式補間（ラグランジュ補間）．
f(x[i]) = y[i] （i=0,1,...,n-1）となる n-1 次以下の多項式 f を考える．

効率的な実装にはなっていない（遅い）です．
Explode("hoge,piyo,,123,", ",") は {"hoge", "piyo", "", "123", ""} を返します．
Explode("hoge,,,piyo,,123,", ",,") は {"hoge", ",piyo", "123,"} を返します．
v = {"hoge", "piyo", "", "123", ""} のとき Implode(v, "-") は "hoge-piyo--123-" を返します．

整数の平方根．（ただし n として ll でオーバーフロー直前みたいなのを引数に与えると動かない可能性が高い）

整数の立方根．
現在は非負整数に対応だが，将来的に負の整数に対応する可能性がある．その場合，Icbrt_s(-8) などは答えが変わる可能性があるので注意．

整数のlog2．
内部で __builtin_clz や __builtin_ffs 系列の関数を使用しています．GCC系以外では動かないかもしれません．
入力が 0 以下なら -1 を返します．
Ilog2の最初の文字は大文字のアイ，2文字目は小文字のエルです．

更新履歴

これ以前の更新履歴はこちら．

Current time: 2023年03月30日02時05分32秒
Last modified: 2020年11月15日15時58分44秒 (by laycrs)
Tags: no_tags
トップページに戻る

Logged in as: unknown user (not login)

ログイン：