kazuma8128’s blog

競プロの面白い問題を解きます

Segment Tree

2018-2019 ICPC, NEERC, Northern Eurasia Finals K King Kog's Reception

問題 https://codeforces.com/contest/1089/problem/K 問題概要 以下のクエリを Q( join t d : 時刻 t に開始して時間 d かかるタスクが予約される (joinでのt は全て異なる) cancel i : i 番目のクエリで追加されたタスクを削除 query t : 現在予約されてい…

動的な Segment Tree のテクニック

区間に(初期値を)代入 普通は区間代入といえば遅延伝搬を使いますが, 遅延なしでも初期値を代入する場合は実は簡単にできます. 方法は, 代入したい区間の各部分木を null に置き換えるだけです. 一応もう少し工夫すると, 区間代入にも一般化できます. 使える…

CodeChef FIBTREE Fibonacci Numbers on Tree

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

区間内の x 未満の値の個数, 区間内の k 番目に小さい値

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

k 番目に小さい値を取得可能な集合を管理するデータ構造

前提 配列(または bitset) Fenwick Tree 平方分割 Trie(動的 Segment Tree) 平衡二分木 おまけ 前提 集合に対して N 個の 追加・削除・k番目に小さい値の取得 のクエリがくるとします. 集合の要素は順序が付けられるものだけ考えます. 要素が非負整数の…

Codeforces Round #404 E Anton and Permutation

問題文 http://codeforces.com/contest/785/problem/E 問題概要 1, 2, ... , n の列が最初にあって l_i, r_i が Q 個与えられるので毎回 l_i 番目の値と r_i 番目の値をスワップしてから全体の反転数を求めよ AC までの思考過程 Editorial 曰く, 想定解は平…

HackerRank Mr. X and His Shots

問題文 https://www.hackerrank.com/challenges/x-and-his-shots/problem 問題概要 一次元上にN個の線分の集合 X とM個の線分の集合 Y がある. 点または線で重なる線分のペア (x, y) (x ∈ X, y ∈ Y) の個数を求めよ. 解法 各 x ∈ X について, Y に含まれる線…

HackerRank Heavy Light 2 White Falcon

問題文 https://www.hackerrank.com/challenges/heavy-light-2-white-falcon/problem 問題概要 頂点に値が振られた木に対する以下のクエリを処理せよ. クエリ1:u-v パス上の各頂点の値に x, 2x, 3x, ... の等差数列を足す クエリ2:u-v パス上の各頂点の…

Educational Codeforces Round 13 F Lena and Queries

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

傾きの単調性が要らない Convex Hull Trick

はじめに 傾きに単調性がなくても insert ができる Convex Hull Trick を書きたいなーと思ったものの, 平衡二分木で書くのはめんどくさそうだし定数倍遅そうとか考えて色々調べてたら, セグメントツリーを使った簡単な方法を見つけたので, 備忘録的に書いて…

Codeforces Round #265(Div.1)E The Classic Problem

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

遅延評価 Segment Tree の一般的な実装方法

この間, AOJ にある Do use segment tree とかいう問題を解きなおしたときに今まで持っていた遅延評価 Segment Tree で無理やり書こうとしたら,無限にバグらせて結局一から書き直す羽目になったので,そのとき考えたことについて書きます. 間違っていると…