A. Common Multiple
$x$ の種類数を出力します．
B. Binary Typewriter
最初に 0 を補うことにすれば，結局異なる文字をまたぐ回数を最小化する話になります．高々 $2$ しか改善できません．あとは run length encoding したときの成分数から決まります．
C. Median Splits
$k$ 以下の要素を $-1$，$k$ より大きい要素を $1$ に置き換えて考えます．中央値が $-1$ の subarray というのは，総和が $0$ 以下であるということです．
手前・中央・後ろのどの $2$ 箇所を $0$ 以下にするかで，$3$ パターンあります．
手前・後ろからとる場合には，それぞれ最小の長さでとるようにして判定します．手前・中央の場合には，累積和で $0\to 0\to 0$，$0\to 0\to -1$，$0\to -1\to -1$，$0\to -1\to -2$ となる部分があるかを探せばよいです．
D. Local Construction
後ろから遡ります．極小を残す操作では，挿入する要素が極小にならないように割り当てます．今までの最大値より大きいものだけを割り当てるというように単純化しても構築できます．
E. Keep the Sum
$a_i+a_j=k$ となるペアがないときは簡単です．ペアがあるとき可能です．次のようにしました．
まず，$a_0+a_j=k$ にします（$(i,j)$ に操作すればよい）次に $a_0+a_{n-1}=k$ にします（$(0,j)$ に操作すればよい）．
そのあと，$a_0+a_{n-1}=k$ を保ったまま，$3$ 回の操作で $1\leq i<j<n-1$ となる $a_i,a_j$ をスワップできます．$(a_0, x, y, a_{n-1}) \to (x,x,y,k-x) \to (x,y,y,k-y)\to (x,y,x,k-x)$ とすればよいです．
中央部分をこれを使ってソートして，最後に $a_0,a_{n-1}$ を $0,k$ になるようにすれば完成です．
F. Maximize Nor
まず $\text{nor}(a_l,\ldots,a_r)$ はセグメント木などで計算可能です．これを計算したときに，$l\leq i\leq r$ を満たす $i$ に対して $ans[i]$ を更新することも双対セグメント木でできます．
実はこれを $O(kn)$ 個の $(l,r)$ でやればよいです．
$r$ を止めて考えるのが簡潔です．あるひとつの桁について考えると，01 列の情報として，最後の $1$ しか関係ないです．つまり入力の列は 00000100000 の形と思って考えればよいです．
すべての桁についてこれをやると，入力の列は $O(k)$ 箇所を除き $0$ だと思ってよいです．
$0$ が続く間は nor の値は 2 種の値が交互に繰り返されます．よってそのうち左端から $2$ つ分の $l$ を試せばよいです．
