多重vectorを可変引数テンプレートで - beet's soil
vector<vector<vector<...... > > > > >みたいなのを再帰的に定義させてほしい— beet (@beet_aizu) 2018年4月8日 vector<vector<...>> みたいなのは普通に Variadic Templates で作れるけどそれだとダメなのかな— すいばか (@suibaka_ku) 2018年4月8日 https://t.co/tUwRlZkjIq— すいばか (@suibaka_ku) 2018年4月8日 すいばか さんに圧倒的感謝🙏🙏😭🙏🙏 以下C++ のコード すいばかさん版：型は最後の引数で決まる template<typename T> vector<T> make_v(size_t a,T b){return vector<T>(a,b);} template<typename... Ts> auto make
典型データ構造まとめ - beet's soil
なんか前回伸びたので 参考 hamayanhamayan.hatenablog.jp ei1333's page 宣伝 beet-aizu.hatenablog.com 以下とりあえず辞書順（そのうち典型度順にしたい） Binary Indexed Tree 一点加算、先頭からの区間和、k番目に大きい値が で可能 library/binaryindexedtree.cpp at master · beet-aizu/library · GitHub 容易に多次元に拡張が可能（実用上は2次元くらい？ library/binaryindexedtree2D.cpp at master · beet-aizu/library · GitHub Binary Trie 二進数を管理するTrie木 全体にXOR、k番目に大きい値、lower_bound等が で可能 library/binarytri
典型テクニックまとめ - beet's soil
いつも忘れるので整理してまとめるぞい 数え上げ Bell Number: 区別できる n 個のボールを区別できない k 個以下の箱に分割する 特にB(n,n)は n 個のボールを任意個のグループに分割する方法の数である。 Stirling Number: N個の数字をK個の非空のsubsetに分割する通り数 Montmort Number: 撹乱順列の個数 ソートして大きいものから考える 区間の端だけ求めると で求められる 候補の区間が複数ある場合は最長のものだけ考える ちょうどK個 = K個以下 - (K-1)個以下 全てのx∈Gに対しf(x)∈Hを数えるとき、y∈Hに対しf^-1(y)=xなるものを数えることもできる 多項式の係数のGCDは積に対して準同型をなす（ c(P)*c(Q) = c(P*Q) sum(C(i,j)) の形は高速に求められることがある（黒白がX,Y枚あって、その
Heavy-Light Decomposition - beet's soil
この記事は 「競プロ!!」 競技プログラミング Advent Calendar 2017 - Adventar の13日目の記事として書いています。 はじめに 先にこっちを見て beet-aizu.hatenablog.com 実装はこれが綺麗 codeforces.com 【HL分解でできること】 HL分解では、木（あるいは森 ）上のパスを 個に分割することができます。 分割後のパスに対して操作を行った後にマージし直すことで、操作を高速に行うことができます。 HL分解を使えるかどうかの条件は、載せるデータ構造（セグ木、BIT）等のみに依存します。 つまり、ある単純な（一直線に並んでいるような）要素列に対しての問題が で解けるなら、 それが木の上のパスになった場合でも で解くことができます。 参考: mathさんのオーダー周りの記事 Heavy-Light Decomposition -
遅延伝播セグメント木について（旧：遅延評価セグメント木について） - beet's soil
もう12月まじ？こわれる はじめに 先にこっちを見て beet-aizu.hatenablog.com 2019/05/06 編集 遅延評価を遅延伝播に変更 問題例へのリンク↓を追加 beet-aizu.hatenablog.com 【はじめに】 これの続きです。 beet-aizu.hatenablog.com 前提としてうし木（普通のセグメント木）までは理解しているものとします。 この記事では後述する の場合だけ取り上げましたがそうでない例が↓の後半にあります。 beet-aizu.hatenablog.com 【遅延伝播セグメント木とは】 ある列に対して連続する区間に対して更新と取得ができるデータ構造である。以降遅延セグ木と略す。 前回のブログでは、要素の集合 と写像 からなるモノイド を考えた。 遅延セグ木では、新たに作用素の集合 と写像 からなるモノイド を追加し、 さらに作用と
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
