ARC082 F - Sandglass - ツバサの備忘録

解法

クエリが時間順で並んでいるので、時刻を進めながらクエリに答えていくことを目指します。
時刻 $t$ のクエリに答えるには、 $r_{i} \lt t$ となるような $r_{i}$ の中で最大の時刻まで時を進めて砂の量を調べ、最後にひっくり返す部分だけシミュレートすれば良いです。
よって、それぞれの $r_{i}$ にて、最初の砂の量が $a$ であった場合にどうなっているか、がわかればよいことになります。
また、砂の量を $a$ で始めたにも関わらず途中で砂時計の上部の砂が空になり、全て下部にたまった場合、砂の量は始め $0(X)$ であった場合と同一視できます。
このような状態になる $a$ は、区間になっているので、その境界を見つけることができればよいです。
途中で空にならなかった場合は、砂時計をシミュレートしていった場合の増減を累積和で記録しておくことで、ある時刻 $r_{i}$ における砂の量がわかります。
よって、あとは $0,X$ と同一視できる区間の境界が求まればよいことがわかりました。
まず明らかに $r_{i} - r_{i-1} \geqq X$ の場合、任意の $a$ が初めから $0$ もしくは $X$ であったとわかります。
そうでない場合も、増減の累積和を確認し、ある時刻に $0(X)$ になる $a$ の区間をマージしていくことで、高速に求めることができます。