コンテスト中AC:A,B

A - Erase by Value

同じ数は消えるので、一旦連続して重複した数について、重複を削除して考えます。
$A_1$ から始めて、単調増加している間は、消すと辞書順では大きくなってしまうので、消さない方がよいです。
そこで、減少に転じた時に、その直前の数(すなわち、 $A_1$ を開始点とした、単調増加な部分の最大値)を消してみます。この時消す数を $A_k$ とし、生成される数列を $B$ とします。

すると、 $A_k$ より後の数を消すと、必ず $A_1,\cdots A_k$ という部分が残るので、この時生成される数列が $B$ より辞書順で小さくなることはあり得ません。よって、 $B$ が辞書順最小となります。

なお、減少に転じない場合もあるので、その場合は末尾の数を削除対象にします。
[提出コード] (https://atcoder.jp/contests/arc133/submissions/28684574)

B - Dividing Subsequence

$P_i,Q_j$ を、それぞれ $a_k,b_k$ とすることを $P_i$ と $Q_j$ を対応させると呼ぶことにします。
また、問題文の制約に沿って生成される $a,b$ を適合列と呼ぶことにします。適合列の要素数と言った時には $a$ (または $b$ )の要素数を指すことにします。

$P_i$ と $Q_j$ を対応させた時に得られる適合列の要素数の最大値は、

$\{P_1,P_2,\cdots ,P_{i-1}\}と\{Q_1,Q_2,\cdots ,Q_{j-1}\}$ から作られる適合列の内、要素数が最大であるもの + 1

です。

添字に着目すると、 $i' \lt i$ かつ $j'\lt j$ を満たすすべての $i',j'$ の適合列の要素数の最大値が計算されていれば、 $i,j$ のときの最大値を計算できます。そこで、添字の問題に帰着させます。　　

$P_i$ と $Q_j$ が対応可能である場合に $A_k=i,B_k=j$ となる配列 $A,B$ を作ることを考えます。

$P$ と $Q$ のあり得るすべての組を $A,B$ に記録します。
例) $P=\{3,1,4,2\}$ , $Q=\{4,2,1,3\}$
$P_1$ は $Q_4$ と対応可能
$P_2$ は $Q_1,Q_2,Q_3,Q_4$ と対応可能
$P_3$ は $Q_1$ と対応可能
$P_4$ は $Q_1,Q_2$ と対応可能
$A=\{1,2,2,2,2,3,4,4\}$
$B=\{4,1,2,3,4,1,1,2\}$

$A,B$ の構築方法は後述します。一見全組を得るのに $O(N^2)$ になりそうですが、エラトステネスの篩と同じ様に $O(NlogN)$ で構成できます。

$B_i$ をキーとして昇順ソートします。すると、 $j \lt i$ なら $B_j \leq B_i$ になります。
一旦、 $B_j=B_i$ の場合を無視すると、

$j \lt i$ を満たす $j$ (つまり、 $i$ より前に出現したもの)のうち、 $A_j \lt A_i$ となる $A_j$ から最大値を得る

問題となります。これはBynary Indexed Treeによって反転数を求める問題の考え方を応用できます。
今回は最大値を得たいので、maxの二項演算が規定されたSegment Treeを使います。Segment Treeの値を保持する配列を $dp$ とします。最初、全て0です。

$dp[A_i]$ を計算したいとき、 $max(dp[0],dp[1],\cdots ,dp[A_i - 1])$ という計算によって、 $A_j \lt A_i$ となる $A_j$ から最大値を得ることができます。
そして、
$dp[A_i]\leftarrow max(dp[0],dp[1],\cdots ,dp[A_i - 1])+1$
と更新すれば良いです。 $B_j = B_i$ の場合ですが、今回はこれを満たす $A_j$ は無視したいです。そこで、 $B_i$ が等しいものについて最大値を全て計算し終わった時点で、一括して上記の更新を行うようにすれば良いです。