A. Operations with Inversions
初期状態で $j$ が消せるならば，どのように操作しても，$j$ が削除されるまでは $j$ が消せる状態が維持されます．
B. Optimal Shifts
最初はかなり難しい問題に感じてしまいましたが．
何回かの操作を同時に行うのではなく，行うたびに $s$ の更新が入るところが重要です．このことから，操作 $d$ は 操作 $1$ を $d$ 回行うことに置き換えても損をしません．
結局操作 $1$ だけを考慮すればよいです．
C. Odd Process
偶数コインと奇数コインを選ぶ枚数を決めたときにどうなるでしょうか．
奇数コインを選ぶ枚数が偶数ならば，スコアは強制的に $0$ になります．
奇数コインを選ぶ枚数が奇数ならば，奇数コインは $1$ 枚を除いて破棄され，最大価値の奇数コインひとつと，偶数コインを価値の高い方から選ぶのが最適になります．
これで枚数 $(a,b)$ を決めたときの最適解が求まります．
$(a,b+2)$ より $(a+2,b)$ が（コイン枚数に矛盾しない限り）上位互換となることを考慮すると，最適解の候補は $a$ が最大値付近である場合および，$b$ が最小値付近である場合の $O(N)$ 通りに限定できます．
D. Fibonacci Paths
（頂点、前回居た頂点）という組が $M$ 通りです．ただしそのような状態すべてから valid な遷移先をとっていこうとすると，遷移数が $O(M^2)$ などになってしまいます．
（頂点、前回居た頂点での値）という組も $O(M)$ 通りです．状態をこの形で持ち，遷移可能な「次の頂点」にのみ遷移させるようにします．ある辺を使う遷移の始状態が $O(1)$ 個になるので，計算量が $O((N+M)\log(N+M))$ 程度になります．
E. Remove at the lowest cost
まず変更クエリがないとして解きます．
最後まで残るものの扱いがちょっと特殊です．
$A[i]=A[j]$ であるような $i,j$ が隣接してこれらに操作を行うとするときには，$B[i]$ が大きい方を消すとしてよいです．残るものは，$A$ が最大かつ $B$ が最小なものということになります．
それ以外の要素の要素ごとの削除コストを考えてみます．
$j$ を固定して，$a_l>a_j<a_r$ となる最大の $l$ および最小の $r$ をとります（なければ $-1,N$ など）．このとき，$i\leq i, r\leq i$ を満たす $i$ はコスト $B_i$ での削除は不可能です．また $l<i<r$ を満たす $i$ はすべて（最大の $A[i]$ を除き）コスト $B[j]$ で削除可能です．これは $i$ に近いものから消していくという方法で達成できます．
結局，結論として，次の貪欲アルゴリズムがあります．
- $B_j$ が小さいような $j$ から順にループする．
- 上のような $l,r$ を求める．$l<i<r$ となる $i$ のうちで未削除のものをコスト $B[j]$ で削除する．
「未削除の $i$ があるのに $B_j$ は削除済」になってしまうとこれは破綻しますが，実際にはそのようなことは起こりません．$j$ を削除する処理が起きたならばそのときに $i$ も削除できているはずだからです．
（タイブレイク問題がなければ，Cartesian Tree で subtree 削除操作を行うと考えると納得しやすいです．今回は変更クエリもあるので木構造を固定して考えようとすると混乱しやすく，元の設定のまま考えた方がいい気がします）．
変更クエリを考慮します．
$B[j]=0$ と変更されると，上のような $l,r$ をとったときに，$l<i<r$ であるような要素の削除コストを $0$ にできます．要素ごとのコストを管理し，クエリでは区間内でのコストを $0$ に変更し，総和を求める．という処理で解くことができます．
変更クエリが来ると「最後まで残るもの」の扱いにも警戒しなければいけない気がしますが，$A[i]$ が最大であるような要素にクエリがきた時点で何もかもコスト $0$ になるのでこれは簡単です．
F. Omega Numbers
$\omega(ab)=\omega(a)+\omega(b)-\omega(\gcd(a,b))$ です．
そこで，次を求めることにします．
- $g, k$ に対して，$\gcd(a_i,a_j)=g$ かつ $\omega(a_i)+\omega(a_j)=k$ を満たす $(i,j)$ の個数
$g$ は $O(N)$ 通り．$\omega(a)\leq 7$ 程度なので，$k$ は $15$ 通り程度でよいです．さらにこの値は次の値の倍数関係に関するメビウス変換です．
- $g, k$ に対して，$g$ は $a_i,a_j$ の公約数 かつ $\omega(a_i)+\omega(a_j)=k$ を満たす $(i,j)$ の個数
これは $g$ を固定するごとに $O(N/g)$ 時間などで計算できて，全体で $O(N\log N)$ 時間です．
