http://agc015.contest.atcoder.jp/tasks/agc015_e
解法
http://agc015.contest.atcoder.jp/submissions/1318194
動画解説と文字解説ではソートしているものが違うので注意。
自分の実装では、配列Xでソートしている。
動画でも文字でも解説があるように、問題を言い換えることができる。
この辺の説明は難しいのですが、動画解説を見るほうが分かりやすい。
以下の流れで答えを導いていく。
1. V[i]を予め座圧しておく (zaatsu関数)
2. 問題を変換する (change関数)
3. dpで解く (dodp関数)
dodp関数の実装は
Solution1(O(N^2)) : dp[i][j] := i番目までの[L[i],R[i]]で[0,j]番目を覆うための組合せ
Solution2(O(N^2)) : dp[i] := [0,i]番目を覆うための組合せ(dp配列使い回し版)
Solution3(O(NlogN)) : Solution2の実装を見ると分かるが、区間和を取っているので、ここをセグメント木で高速化している
Solution4(O(N)) : change関数がO(NlogN)なので、ココまでやる必要はないのだが、R[i]が広義単調増加しているのを利用して、累積和でココまで高速できる
