ARC 115-E

ARC 115-E （LEQ and NEQ）

 

問題リンク

 

 

便宜上、 X を 0-indexed にします。
i 番目まで見たとき、最後のものが x\ (=0,1,2,\cdots) である場合の数を f_i(x) として、これを管理することを考えます。
同じところはまとめて管理すると、\Big((a_0, b_0), (a_1, b_1), \cdots, (a_k, b_k)\Big) のようなスタックで表せます。これは a_{t-1} \le x \lt a_{t} の範囲では、 f_i(x) = b_t であることを示します。ここで a_0 = b_0 = 0 です。

i-1 番目まで見たときの場合の数の合計を z とすると、0 \le x \lt A_i のとき f_i(x) = z - f_{i-1}(x) 、 x \ge A_i のとき f_i(x) = 0 です。

なお z は c_i=\sum (a_i-a_{i-1}) \times b_i を持っておくと O(1) で更新できます。

 

スタックの更新は愚直にやると O(N) かかってしまいますが、全体に掛ける倍率（1または-1）および全体に足す数を別で管理することで、ならし O(1) で更新できます。

以上より、全体で O(N) でこの問題を解くことができます。

 

ACコード（PyPy3）