F

H<=Wになるように適宜transposeする。

に1, .に-1を割り当てた配列の2次元累積和上でS(ul)-S(ur)-S(dl)+S(dr)=0 となる点を探索すればよい。

行を2つ選ぶ。つまりu,dを全探索する。列T[i]=S(ui)-S(di) をこのように定めると、T[x]=T[y]を満たすような(x,y)のペア数がそのままu,dを固定したときのl,r の選び方に対応する。残りはzero-sum-rangesをやればよい。

計算量はO(H^2W)で相当ギリギリ、TLEを2回踏んだ。コンストラクタは遅い！

期待値DPとかと一緒で「この状態から出発したとき最大でどこまで倒せるか」を状態として持つようにする。

dequeはランダムアクセスできるんだよな～→k回ローテーションする必要があり、終了...... 大人しく先頭の位置 mod Nを管理

値の候補が少ないので現在の地点と現在までの累計XORを持ってBFS

めんどい

Pythonとかだとうまく書ける？

言い換えると区間の重なりであって最も外側が互いに重ならないようなものを2つ選ぶ問題になる。

各区間が最大で何重になっているかをまず調べる。これは終点でソートした後Segment Treeで区間内の最大を管理していけばできる。

あとは区間を1つ/2つ選び重なりの合計を最大化する問題になるが、これもSegment Treeでできる。