実用的に高速 コード SubsetSumNewton.cpp \( O(n + t\log t) \) と SubsetSumRecursive.cpp \(O(n + t \log^2 t)\) SubsetSumNewton.cpp · GitHub 概要と意訳 Ce JinさんとHongxun WuさんのA Simple Near-Linear Pseudopolynomial Time Randomized Algorith…

概要 Longest increasing subsequence 問題はFenwick treeを用いてO(n log m)で解ける（nは列の長さ、mは要素の最大値） 実行時間としては二分探索を用いる方法と大きな差はない 動機 今朝のCodeforces Round #468の他人のコードを見るとLISをFenwick treeで…

問題 二次平面上に軸に平行な長方形がn個与えられる。 入力として与えられる長方形について、どの二つの長方形も、 共通部分を持たない 一つの長方形がもう一つの長方形の真に内側にある のどちらかを満たすことを保証する。これらの長方形の包含関係から根…