Suuさんのブログ

区間に漸化式で表される数列を足すタイプの imos法

No.1172 Add Recursive Sequence - yukicoder

この問題のことです

頭が悪くて解説がすぐには理解できなかったので整理用にメモ

めんどうなので $a, c$ は 0-based-index, $c$ は反転して考えます

$[l, r)$ に足す

というのを

$[l, n)$ に $a _ 0, a _ 1, \ldots, a _ {n - l - 1}$ を足して

$[r, n)$ から $a _ {r - l}, \ldots, a _ {n - l - 1}$ を引く

と考えると

$[i, n)$ に $a _ j, a _ {j + 1}, \ldots$ の定数倍を足すことを考えればいいです

足される数列を左から見ていきます

ほんとに $[i, n)$ に足したら $O(N)$ かかってしまうので, とりあえず $x _ i$ にだけ足すことにします

$x _ i$ に対して足すクエリをすべて処理した後の $x _ i$ が

$x _ i = \displaystyle\sum _ {j \in Q} p _ j a _ j$

みたいにかけたとします ( $p$ はいい感じの定数倍)

ここから

$\displaystyle\sum _ {j \in Q} p _ j a _ {j + 1}$

を求めることができれば, またクエリの左端が $i + 1$ であるようなものについてだけ足すことで $x _ {i + 1}$ を求めることができます

ここで, $0 \le i \lt K$ について

$y _ i = \displaystyle\sum _ {j \in Q} p _ j a _ {j + i}$

という数列を考えてみます ( $x _ i = y _ 0$ )

ここから

$y _ K = \displaystyle\sum _ {j \in Q} p _ j a _ {j + K}$

を求めることはできるでしょうか？

線形性があるので

$y _ K = \displaystyle\sum _ {i = 0} ^ {K - 1} c _ i y _ i$

と書けます (適当に代入してまとめれば出ます)

ということで, $(y _ 0, \ldots, y _ {K - 1})$ を持ちながらクエリを左から足していけば求まります

$y$ を $K$ 項常に持っているので, クエリでも $K$ 箇所に足すことになります

これは $a$ を $N + K - 1$ 項目まで前計算しておけば $O(K)$ で簡単に処理できます

$y$ の遷移も $O(K)$ でできるので, 全体で $O((N + M)K)$ ですべてのクエリを処理することができます

実装 (せっかくなので雑に構造体にしてみた)

#796623 (C++17) No.1172 Add Recursive Sequence - yukicoder