Pinely Round 2 (Div. 1 + Div. 2)

　pretestはEまで。

コンテストへのリンク

コンテスト後のツイート

D 同じ行にURが偶数個なくてはダメ。LRも同様。
E 後ろからDPして、各クエストを始点にしたらどれくらい時間がかかるかを求める。xに開始すればyに終わるというペアがたくさん得られるので、xでソートすれば、yの累積maxを使うことで、各[x,y]についてxから初めて全て終わらせるまでの時間が分かる。

— titia (@titia_til) August 30, 2023

F. Divide, XOR, and Conquer

　こたつがめさんの放送の振り返りを見てAC。

　いや以前に、この放送や公式解説を見たときは分からなくてしばらく放置していたのだけど、今もう一回きちんと見たら理解できた。

　区間DPでいけそう、と言われればそういう気はしてくる。（n=10000でも想定計算量が二乗の可能性があることに注意しよう）

　ただ、区間DPが二乗で済むと思いにくいし、また、空間計算量が線形で済むと気付きにくい。

　区間DPでいけると言われれば自然な解法に思えるが、それでいけるとは思いにくい問題な気がする。

・Sを累積xorとする。

・最上位bitに注目するのは自然。

・長さが長い区間から区間DPしていく。

・[l, r]でS[l]とS[r]の最上位bitが同じなら、[l, n], [n, r] for any n（ただし、それぞれの区間は元のものより短い）に遷移できる。

・[l, r]でS[l]とS[r]の最上位bitが異なるなら、そのbitをxとすると、[l, n]に遷移できるのは、S[l]^S[n]のx bit目が異なるとき（[n, r]も同様）。これを覚えておきたいが、そのとき、「S[l]が左端になるときは、右端とx bit目が異なれば良い」とさえ覚えておけば良い。

・この後、xと異なるyについて、「S[l]が左端になるときは、右端とy bit目が異なれば良い」を覚えておきたい状況が存在するかもしれない。そのため、(1<<x)|(1<<y)と記録しておけばOK。