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

問題文 http://codeforces.com/contest/932/problem/F 問題概要 問題文が短いので省略 解法 木DPのイメージでやると, 頂点 v に対して dp[v] = min{ a[v] * b[u] + dp[u] } (u は v の子孫) という式が立つので, Convex Hull Trick で求まりそうな形になりま…

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