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

クエリの定義 基本的なテクニック 値の変更なし ver オフラインクエリ rank kth_min オンラインクエリ rank kth_min まとめ 値の変更あり ver X[p] の値を v に変更 rank kth_min その他 値の変更/挿入あり ver クエリの定義 長さ N の整数列 X に対して, 以…

問題文 http://codeforces.com/problemset/problem/678/F 問題概要 直線の式の集合 S があります（最初は空集合）. 以下の3種類のクエリを N 個処理せよ 追加 ： 直線の式 f_i(x) = a * x + b を S に追加 削除 ： x 回目のクエリで追加した直線の式を削除 …

問題文 http://codeforces.com/contest/464/problem/E 問題概要 頂点数 n 辺数 m の無向グラフが与えられるので, 頂点 s から 頂点 t までの最短経路を求めよ. 存在しない場合は-1, 複数ある場合はどれでもよい. ただし辺のコストは, 辺ごとに x_i が与えら…

問題文 https://www.codechef.com/problems/GPD 問題概要 頂点数 N の根付き木が与えられる. 各頂点には正整数のキーが付いている. 以下の二種類の Q 個のクエリをオンラインで処理せよ.クエリ１：頂点 v の子に, キー k の付いた新しい頂点 u を増やす クエ…