A. Zero Sum
$1,-1$ の個数の parity が不変量になります．
総和 mod 4 といってもよいです．
B. Yet Another Constructive
累累積和が $0,1,\ldots,K-1$ を周期的に並べたものになるようにすればよいです．
C. Inversion of a Subsequence
入力は， $(0,0),(0,1),(1,0),(1,1)$ の個数に圧縮できます．
$0$ 手をまず判定します． $sum A = 0$ および $sum B=N$ を判定します．
$(0,1)$ が奇数組ならば， $1$ 手です．他のインデックスは好きに必要なところだけ操作に含めればよいので．
そうでなければ $2$ 手です． $(0,1)$ が奇数組ある状態に変換できることが少し場合分けをするとチェックできます．
D2. XOR Sorting (Hard Version)
雑な log^2 が TLE，確かに制約が大きめ．
完全二分木の形のセグメント木を使って， $O(N+Q\log N)$ で解けます．
各ノードに min, max を持っておき，子をマージして親にするときに，「left max > right min」となっていたらそこで $k$ の必要量が増えます．
適切にモノイドを作れば，セグメント木に対する点変更と，prod_all という形で処理できます．
E. Build a Tree
パスグラフだけで作れます．
ある頂点について
- マイナス：「右から来て右に出る」
- プラス：「左から来て左に出る」
とすると，
-----00+000++++
のような構成で全部作れます．
F. Paths on a Grid
「 $A$ を通るならば $B$ も通る，逆も然り」という関係のときに同値．
という関係による同値類分解を求めよということです．
これは， $s$ を根とする dominator tree と， $t$ を根とする dominator tree を作れば，
- $u$ は木 $T_A$ における $v$ の祖先
- $v$ は木 $T_B$ における $u$ の祖先
の両方が成り立つことと同値です．
あとはこの関係で同値類分解すればよいです．
- $T_A$ において，先祖側から dominator 関係 $a\to b\to c$ がある
- $a,c$ は同じ同値類に属する
を仮定します．パス $P$ について，
- $c\in P\implies b\in P\implies a\in P$
- $a\in P\iff c\in P$
ということで，このとき $a\in P\iff b\in P$ および $b\in P\iff c\in P$ が示せます．
すると結局， $a,c$ の同値関係は $a,b$ の関係と $b,c$ の関係から生成できます．
したがって，同値関係は $T_A$ における直接の親子から生成できます．（もう少し考えると，おそらく両方の木で互いに親子であるという関係だけでよいはず）
