2020-06-01から1ヶ月間の記事一覧
試してないのでわからないのですがtie(t->r,t->r->l,t)=make_tuple(t->r->l,t,t->r);で木の回転が出来そう?— 5%の確率で橙パフォをとるhotman (@hotmanww) October 30, 2019 昔考えたやつをブログ化 //npはnodeのポインタ、b=1で右回転 ch[1]は右の子、ch[…
0.はじめに 僕自身が学んでる途中なので嘘などあるかも知れません 高速化に目覚めたので書いていきます これ使うだけじゃ速くならないと思います SIMD使う前の準備だと思って練習してます atcoderのC++(GCC 9.2.1)準拠です 1.入出力 int main(){ int res; as…
staticな変数を使ってこう出来ます 最初に前処理が必要な競技プログラミングのライブラリに重宝します void f(){ static bool init=0; if(!init){ init=1; //初回実行処理 } //毎回実行する処理 }
gcc拡張により 関数の前に__attribute__(( constructor))を付けると最初に 関数の前に__attribute__(( destructor))を付けると最後に呼ばれます __attribute__((constructor)) void constructor() { cin.tie(0); ios::sync_with_stdio(false); cout<
コード例は抽象化してません あしからず 1.がちがちの動的セグ木を使う コピペありの環境なら一番いいです 思想としてはポインタを使って必要になった時にノードを作るです 構築O(1)です template<typename T> struct dynamic_segment{ struct node; using np=node*; str</typename>…
追記 テストケースを見れるサイトを公開しました library-checker-testcases.hotman78.com コマンドプロンプトを開きます gitを入れます(手順は各自調べてください) cdコマンドで適当なディレクトリに移動して下の2つのコマンドを打ちます sudo git clone ht…
ark4rk.hatenablog.comこれを事前に読んで欲しいです。 分割統治法の方針でセグ木に乗せられます これにより、 点更新 [l,r)間の連続部分列における総和の最大値を求める が出来ます からなるベクトルを考えると、これがモノイドになっています。試しにベク…
拡大係数行列を考える。 この時、の時のみ解が存在する事が知られている。 転置行列についてもrankは同じであるため、で計算が出来る。 からでが求められる事から転置行列においては2倍の定数倍高速化も可能である。