A. Binary Literature
それぞれ「$0$ が半分以上」「$1$ が半分以上」のうちひとつ以上が成り立ちます．うまく $2$ つを選び，文字種を入れ替えるなどして考えると，「$0$ が半分以上」のものが $2$ つあるときに解けばよいです．
各 $k$ について $k$ 個目の $0$ を同時に作るようにしながらそれぞれの部分列を作っていくと，のべ $4N$ 文字のうち $N$ 回以上がまとまるので，コスト $3N$ 以下になります．
B. Almost Sorted
条件を満たす列は，321|4|765|8|9 のように，123456789 を区切って各区間を reverse したようなものです．
長さ $n$ のこれは $2^{n-1}$ 個あります（各位置を区切るかどうか）．あとは手前から決めていけばよいです．
C. Complete the MST
$w_i>0$ ということで，補グラフでなるべく重み $0$ を使って，残りを今ある辺で作るという雰囲気になりそうです．そこで補グラフの連結性を考えます．
補グラフがサイクルを含む場合，ここで XOR を調整できます．補グラフで重み $0$ の辺で可能な限り連結させたあと，残りを既存の辺で連結させます．以下補グラフは森としてよいです．
先に，補グラフの辺を全部使う場合の処理をします．この場合，XOR を $0$ にするということから最適な辺重みの和が決まります．
次に補グラフで使わない辺があるとします．使わない辺をひとつ固定するごとに解きます．使わない辺のところで XOR は調整可能なので，XOR の制約は無視できます．使わない辺は全探索します．補グラフが森であることからこれは $O(n)$ 通りで，$n=O(m^{0.5})$ です．よって毎回愚直に最小全域木を求めても $O(m^{1.5})$ 時間で解けることになります．
D. Swap Pass
$a_i=i$ であるような点を無視します．
辺 $(0,i)$ と辺 $(i,i+1)$ を考えます．これらは交差せず描けます．
順列を例の方法でサイクル分解します．辺 $(i,i+1)$ を使っていきます．これは $i,i+1$ が異なる連結成分にあるときには連結成分のマージに相当するので，サイクルをひとつにできます．あとは $(0,i)$ を適切に使えば条件を達成できます．
E. Tree Calendar
まず DFS 順が決まります．優先度の高い子は，どの時点においても書かれている値が小さいことが示せるからです．
さらに，$\sum a_v\cdot \mathrm{depth}[v]$ が単調減少量であることに注意します．
したがって，「$K$ ステップのシミュレーション」が高速に行えれば，答は二分探索可能になります．
ある $i$ を下げるフェーズでは，帰りがけ順が $i$ 番目であるような点に向かっておりていきます．ここから，そのようなフェーズ全体でのステップ数やシミュレーション結果がまとめて求められます．端数分は愚直に動かせばよいです．
F. Optimal Encoding
DAG の transitive reduction を求める問題で，計算量を問わなければ，
- 辺 $i\to j$ がある．
- その辺を使う以外に $i$ から $j$ へのパスは存在しない．
というような $i\to j$ をすべて残すことになります．
残る辺としてありうるものを全列挙します．ある区間 $[l,r]$ があるとき，この中の $a_i<a_j$ を満たす組に $i\to j$ が張られますが，このうち候補とするのは，$a_i<a_k<a_j$ となる $k$ がこの区間内に存在しないときだけでよいです（区間内のソート順で隣接するペアだけでよい）．mo のアルゴリズムでこのようなペアは全列挙できて，$O(n\sqrt{q})$ ペアということになります．
これらが全列挙できたら，それぞれが答に寄与する時刻を求めます．
- $i\to j$ がはじめて張られる時刻から，
- $i\to j$ に長さ $2$ 以上のパスが出来る時刻まで
の区間加算という形です．この $2$ 種の時刻を求めるのが課題です．reverse して $2$ 回計算することにして，以降 $i<j$ を仮定します．
前者の時刻は，$i$ について昇順に処理することにします．$L\leq i$ であるような区間を対象として，$j\leq R$ であるような区間番号の $\min$ ということなので，これはセグメント木で処理できます．
後者の時刻を求めます．まずパスの形状について考えます．$j$ の直前の位置 $k$ を考えます．
- $k<i<j$：$k,j$ を同時に含む区間があることが必要で，これがあればパス $i\to k\to j$ がある．
- $i<k<j$：$a_i<a_k<a_j$ かつ $i<k<j$ となるような $k$ がある $(i,j)$ は，最初の候補列挙の対象外なのでこれはない．
- $i<j<k$：$i$ からのパスがはじめて $j$ の右側に行くときのことを考えると，$a_i<a_{k’}<a_j$ かつ $j<k’$ となる $k’$ の存在が必要である．このときパス $i\to k’\to j$ がある．
結局長さ $2$ のパスしか考えなくてよくて，中継点 $k$ は，
- $i$ の左で $a_i<a_k<a_j$ となるもののうちで最も右寄り
- $j$ の右で $a_i<a_k<a_j$ となるもののうちで最も左寄り
だけ考えればよいです．これらの候補は wavelet matrix などで求まります．このパスが実現する時刻は，$i\to j$ が使えるようになる時刻と同じように計算できます．オンラインクエリの形でこれを実装できるようにした方が実装が簡単だったので，私は永続セグメント木を持ち出しました．
全体として $O(n\sqrt{q}\log n)$ のような計算量です．
