問題概要
長さ$ \ N \ $の数列$ \ A \ (a_1,a_2,\ldots,a_N) \ $があり、全ての要素は$ \ 0 \ $である。
以下のようなクエリが$ \ Q \ $回にわたって与えられる。全て処理した後の数列$ \ A \ $の最大値を求めよ。
- $A_{l_i},A_{l_i+1},\ldots,A_{r_i} \ $に$ \ v_i \ $を加算する。
制約
- $1 \leq N \leq 10^{18}$
- $0 \leq Q \leq 10^5$
- $1 \leq l_i \leq r_i \leq N$
- $-10^9 \leq v_i \leq 10^9$
解説
$N \ $が大きいため、長さ$ \ N \ $の配列を用意することはできません。座標圧縮をしてからいもす法をしましょう。
