Disjoint sparse table を使った素直な解法は \(8\ \mathtt{bytes} \cdot C\lceil N \log (N) \rceil \sim 1144\ \mathtt{MiB}\) となり、メモリ制限を守れません。

そこで、disjoint sparse table の最初の方の段（↓のリンクでは 5 段）を省略して、短いクエリはその都度ナップサック問題を解くことにすると、ギリギリ収まります。

Rust 830 ms, 802056 KiB