このブログの小ネタ記事をまとめときます 遅延評価 Segment Tree の一般的な実装方法 - kazuma8128’s blog 遅延セグ木の抽象化と非再帰化の話 傾きの単調性が要らない Convex Hull Trick - kazuma8128’s blog 一般のCHTの話 Mo's Algorithm について - kazum…

昨日の CodeChef の July Lunchtime 2018 に参加したときに思いついたのでメモ.※何も見ずに書いてるからもしかしたら間違いだらけかもしれないので注意です. ゼータ変換 競プロで使うゼータ変換(?)は, 各集合について, その上位または下位集合の和を求めるや…

問題文 http://codeforces.com/contest/375/problem/D 問題概要 頂点に色が付いたサイズ N の根付き木がある. 根は 1. 以下の Q 個のクエリに答えよ. v k : 頂点 v の部分木に k 個以上含まれるような色の種類数を出力 解法 前に解いたときは木上 Mo で unor…

問題文 https://www.codechef.com/problems/FIBTREE 問題概要 サイズNの木がある. 各頂点は値を持っている(初期値0). Q個の以下のクエリをオンラインで処理せよ. クエリ１：頂点 x から頂点 y へのパス上の各頂点に順番に fib(0), fib(1), ... , fib(k) のフ…

HL分解*1でパスクエリができることは知ってたけど同時に部分木クエリも行えることを知ったのでメモ. (もしかして割と常識なのかな？)これ https://codeforces.com/blog/entry/53170 弱い方のHL分解 元々持ってたライブラリでは, 一回 dfs で各部分木のサイズ…