ei1903の競プロメモ

競プロの解説など

HOJ 1530 - Increasing Sequence 2

HOJ 解説

問題概要

長さ $\ N \$ の数列 $\ A \ (a_1,a_2,\ldots,a_N) \$ が与えられる。
以下のようなクエリが $\ Q \$ 回にわたって与えられる。

$a_{x_i} \$ に $\ v_i \$ を加算する

$i \$ 番目までのクエリを処理した時点での数列 $\ A \$ を数列 $\ A_i \$ としたとき、 $A_1,A_2,\ldots,A_Q \$ のうち広義単調増加であるものの個数を求めよ。

制約

$2 \leq N \leq 3 \times 10^5$
$1 \leq Q \leq 3 \times 10^5$
$1 \leq a_i \leq 10^9$
$1 \leq x_i \leq N$
$1 \leq v_i \leq 10^9$

解説

$(1 \leq i \leq N - 1) \$ を満たす整数 $\ i \$ について、 $a_i \leq a_{i + 1} \$ を満たすならば、数列 $\ A \$ は広義単調増加であると言えます。
そのため、予め上記の条件を満たす $\ i \$ の個数を数えておき、各クエリにおいて更新された箇所の値をその前後の値と比較することでこの個数を更新すればよいです。
よってこの問題は $\ O(N + Q) \$ で解くことができました。