A. Equal Occurrences
出現回数 $k$ を全探索．$k$ 回以上出現するものの種類数を数えます．
B. Merging the Sets
ある選び方が条件を満たすなら，その選び方に何かを足したものも条件を満たすことに注意します．
$2$ 個以上削除して条件を満たすものがあるならば，$2$ 個削除して条件を満たすものがあります．
するとさらに $1$ 個削除して条件を満たすものが $2$ 個，$0$ 個削除して条件を満たすものが $1$ 個あります．よって $1$ 個以下の削除個数で条件を満たすものが $3$ つあります．
このことから削除個数 $1$ 個以下のものをすべて調べればよいです．
C. Wrong Binary Search
$i$ が good になるのは
- $a[i]=i$
- $j<i$ ならば $a[j]<i$
- $j>i$ ならば $a[j]>i$
が成り立つ場合です．そうならば good であること，そうでないならば good でないことどちらも簡単に示せます．
構築はまず $s_i=1$ の部分は確定．その間は …101… のように間にひとつだけ $0$ があるということは起こりえないことがわかります．$0$ が $2$ 個以上並ぶ部分については降順に入れておけば大丈夫です．
D2. Max Sum OR (Hard Version)
ある桁について，$(a_i,b_i)$ が $(0,0)$ であるような $i$ と $(1,1)$ であるような $i$ が両立しないように組めれば理論値達成です．これが可能であることを示し，構築します．
組 $(R-L,L)$ に関する帰納法をします．
$2^k\leq R$ を満たす最大の $k$ をとります．$L < 2^k \leq R$ のとき，$x+y=2^{k+1}-1$ となる組をなるべく作ったあと，手前または後ろで余る $[L,M]$ や $[M,R]$ の形の区間での構築に帰着します．組 $(x,y)$ ではどの bit も $(0,1)$ や $(1,0)$ の形でしか使っていないのでこの場合は帰納法の仮定よりよいです．
$2^k\leq L\leq R$ のとき，$2^k$ の bit は何をやっても $(1,1)$ で使えるので，これを無視して解いてもよいです．よって $(L-2^k,R-2^k)$ の場合に帰着できるのでこれも帰納法がまわります．
E. Yet Another MEX Problem
「mex 以上の要素数」を数えますが，「現れない数 $a$ を選び，$a$ 以上のものを数える」としてもよいです．
$a$ を決めると，最大スコアは「$[\mathrm{prev}(a)+1,i]$ に現れる $a$ 以上の要素数」です．ただし $\mathrm{prev}(a)$ は，$i$ 以下での最後の $a$ の出現．出現しない場合には $-1$ などとします．
この値を $ans[a]$ として，列 $(ans[0],ans[1],ans[2],\ldots)$ を考えます．$i$ をインクリメントしながらこの列 $ans$ を更新していくことを考えると，区間加算・点更新と全体 max 取得ができればよいことになります．
F. Bubble Sort
まず sort() 関数の戻り値は，各 $j$ に対して $a[i]>a[j]$ となる $i$ の個数を数えてその $\max$ です．すべての順列に対してこれを考えると，結局次のようにするのと同じです．
- 各 $i$ に対して $0\leq a[i]\leq i$ となる $a$ を選ぶ（$0\leq i\leq n-1$）．
- $b[i]=\max(a[0],\ldots,a[i])$ とする．
$m$ 個の条件も，$l[i]\leq b[i]\leq r[i]$ の形の $O(m)$ 個の条件に置き換わります．
条件の来る $i,l[i],r[i]+1$ などでもろもろ座圧しておきます．座圧後の列を $x_0,x_1,\ldots$ とします．
自明な解法として，$\mathrm{dp}[k]$ を，$b[i]=k$ となる列を定める方法として，$i=0,1,2,\ldots$ 順に更新していくというものがあります．
重要な計算量改善として，$x_j\leq k <x_{j+1}$ となる $j$ しか状態として持つ必要はありません．
- $i_1$ において $[x_{j_1},x_{{j_1}+1})$
- $i_2$ において $[x_{j_2},x_{{j_2}+1})$
であるときの間の定め方ですが，道中で現れる項については，$x_{j_2}, x_{j_2+1}$ との大小関係しか関係がありません．
これで状態数を $O(m)$ 状態にして，遷移も階乗・階乗逆元・pow でかけるので，全体で $O(m^2\log m)$ 時間などで解けます．
