公式解説とほぼ同方針ですが、少し変わった行列積で計算する方法です。

管理する値の定義

各非空な区間 \([l, r[\) に対して、\(2 \times 2\) 行列 \(a ^ { [ l, r [ }\) を、\(a ^ { [ l, r [ } _ { i, j }\) が \(l - 1 + i\) から \(r - 1 + j\) まで行く経路の個数であるとして定めます。ただし、\([l, r[\) の外にある障害物は、仮にあってもないものとして計算します。

値のマージ

\(l \lt c \lt r\) とします。\(l - i + 1\) から \(r - j + 1\) に行く経路はかならず \(c - 1, \ c\) のいずれかを通ります。そこに障害物があるかどうかという問題も、先述の定義で無視した部分があり不安になるかもしれないのですが、\([l, c[, \ [c, r[\) のいずれかには入っているので、大丈夫です。そこで包除原理より、

\[ a ^ { [ l, r [ } _ { i, j } = a ^ { [ l, c [ } _ { i,, 0 } a ^ { [ c, r [ } _ { 0, j } + a ^ { [ l, c [ } _ { i,, 1 } a ^ { [ c, r [ } _ { 1, j } - a ^ { [ l, c [ } _ { i,, 0 } a ^ { [ c, r [ } _ { 1, j } \]

と計算できます。もしくは、次のように表すことができます。

\[ a ^ { [ l, r [ } = a ^ { [ l, c [ } \begin {pmatrix} 1 & -1 \\ 0 & 1 \\ \end{pmatrix} a ^ { [ c, r [ } \]

です。これはもちろん結合的な演算です。（単位的でもあります。）

長さ \(1\) 区間の値

障害物がある場合、

\[ \begin {pmatrix} 0 & 1 \\ 0 & 0\\ \end{pmatrix} \]

となります。一方、ない場合、

\[ \begin {pmatrix} 1 & 2 \\ 1 & 1 \\ \end{pmatrix} \]

となります。

まとめ

この演算をセグツリーに乗せると良いです。 座標圧縮をするか、初期値の \(2\) 冪乗を前計算しておきポインタベースのセグツリーに乗せるかしましょう。