メメメモモ2023-07-09 G - Distance Queries on a Tree 以下の問題の解説を理解するための知識をまとめてみました。 atcoder.jp 繰り返し二乗法 繰り返し二乗法とは、x1, x2, x4, x8, x16, ... を組み合わせて、xnを高速で計算するアルゴリズムです。 x1, x2, x4, x8, x16 は、二乗していけば、簡単に求めていくこ… 2023-05-14 037 - Don't Leave the Spice（★5） atcoder.jp DPをしつつ、セグメント木で高速化する。 普段は配るDPで実装することが多いが、この問題では貰うDPで実装するほうが良さそう。 dpの更新は、セグメント木から前段のLからRの間の最大値を取得する。 セグメント木の更新は、dp[i]の値を一通り一気… 2023-05-14 036 - Max Manhat
