A – Parallel Universes
$4$ 種の辺 $(0,0),(0,1),(1,0),(1,1)$ があるグラフで，両成分の反転ができて，両成分で連結にしろという問題です．$2$ 番目の成分について常に連結を保てという縛りがありますが，これは出力のときに順番を調整するだけでよいです．
$N\geq 4$ なら常に Yes です．$N=4$ の場合を何らかの方法で解いておき，帰納的にその解を延長します．
頂点集合 $S$ （$|S|\geq 4$）で目的を達成できているとして頂点 $v$ を追加します．$v$ から $S$ への辺で $(0,0),(1,1)$ のものがあればそれを採用すればよいです．$(0,1),(1,0)$ の両方があるなら何もしないでよいです．$(0,1)$ だけなら適当なひとつを反転すればよいです．
B – Three Arrays
適当な変数変換により $D_i=0$ の場合に帰着できます．すると操作は可換になるため，列を適当な順に並べ替えてもよくなります．$B$ が単調増加になるようにすると，$B$ 側の操作を一度選んだらそこから先はずっと $B$ を選ぶとしてよいです．あとはそのようなすべてのパターンを計算します．
C – Burenka and Pether
読解として $k$ は与えられるのではなく自由に選ぶなので注意…．
遷移可能の条件は，適当な前計算によって単に「$R[i]$ が与えられている．$i<j<R[i]$ かつ $x_i<x_j$ のときに $i$ から $j$ に遷移可能」となります．
クエリは次の貪欲により解けます：$i$ から $j$ に遷移可能かつ $x_j\leq x_{v}$ を満たす $j$ のうちで，最も $x_j$ が大きいものへの遷移を繰り返す．添字が小さく値が大きい場所の方が，その次の手の行き先の集合が大きいことが，遷移可能の条件から分かるからです．
あとは次と同じことをします．
$x_v$ について昇順にクエリをソートして，Link Cut Tree によって有向木を管理します．有向木の各頂点には，その遷移先がいつまで利用可能であるかを持っておき，クエリのたびに始点から根までのパスで壊れているところがあればなおすということを繰り返します．これで Link Cut Tree に対する操作回数が 1.5 乗オーダーになります（最悪ケースが作りにくいタイプなので思ったより高速？）．
ある点の遷移先が次に変更されるのはいつであるかを求めるのは単に $x_v$ より大きいものだけを対象とする range minimum query です．
D – Almost Certainly
無視するもの $1$ つずつを決めると，可能であるならば，コストは sum だけから決まります．
可能なもののうちなるべく大きな $a-b$ が大きくなるような $(a,b)$ を無視したいということになります．可能かどうかは削除後に b,a がカッコ列になっているか（すべての a_i,b_i をソートして b を開きカッコ，a を閉じカッコにする）ということです．削除してカッコ列が維持できるのは，もともと間の部分の累積和が常に正になっているということです．
結局，$b_i$ で $+1$，$a_i$ で $-1$ するという累積和（これは常に非負）を考えて，正になる部分の両端点が候補ということになります．言い換えれば区間 $[b_i,a_i]$ の和集合の両端で，区間の和集合を適当に管理すれば解けるということになります．
