♥沙耶花の備忘録♥

ARC115-E LEQ and NEQ (TLEに近い解法)

包除原理を念頭に, 次のようなdpをしまふ.

$dp[i][j]$ 今まで条件に違反した回数の偶奇が $i$ で最後に選んだ値が $j$ であるような通り数

新しいdp配列をndpとすると, 遷移式は次のようになりまふ.

$ndp[i][j] = 0$ ( $j$ が現在見てる $A$ の値に比べて大きいとき)
$ndp[i][j] = (dp[i][0] + dp[i][1] + ... + dp[i].back())$ ( $j$ がひとつ前の $A$ の値に比べて大きく, 重複しないとき)
$ndp[i][j] = (dp[i][0] + dp[i][1] + ... + dp[i].back()) + dp[i \oplus 1][j]$ ( $j$ がひとつ前の $A$ の値以下で, 重複するかもしれないとき)

$j$ の値の範囲が大きくなりすぎることをいったん無視すると, これは遅延セグ木でin-placeに更新できまふ. 具体的には, ノードにdpの値と区間幅を, 区間に作用させる演算として一次関数を用意すれば良いれふ.

$j$ の値が大きくなりすぎる問題れふが, $A$ をソート&重複削除すると $B$ になるとして, $(0,B_1],(B_1,B_2],...$ を遅延セグ木のノードに対応させれば良いれふ.

ご覧のようにこの解法は2000msとTLEに近いれふ. しかし, 沙耶花ちゃんは日々を真面目に生き, 少しずつ徳を積んできたためこれで落ちることはありません.