問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

整数列 $P$ に対して, $P$ の最長増加部分列の長さを $\operatorname{LIS}(P)$ と書くことにする.

$(1,2, \dots, N)$ の並び替え $A,B$ が与えられる. 次の操作を $0$ 回以上行うことができる.

$1 \leq i \leq N-1$ となる整数 $i$ を選び, $A_i$ と $A_{i+1}$ を, $B_i$ と $B_{i+1}$ をそれぞれ交換する.

操作後における $\operatorname{LIS}(A)+\operatorname{LIS}(B)$ の最大値を求めよ.

制約

$2 \leq N \leq 3 \times 10^5$
$A,B$ は $(1,2, \dots, N)$ の並び替え

解法

隣接交換を何回もできるので, 次のことが従う.

$A$ を任意の $(1,2, \dots, N)$ の並び替え $A'$ と等しくすることができる.

また, $A_i$ が動く時, $B_i$ も同じ場所に動き, それ以外の時は動かないので, 次のことも従う.

何回かの隣接交換によって出来る2つの並び替えの組 $(A', B'), (A'', B'')$ において, $A'=A''$ であること, $B'=B''$ であることは同値である.

そして, 以下も従う.

何回かの隣接交換の結果を $(A', B')$ とする. このとき, $\operatorname{LIS}(A')+\operatorname{LIS}(B')$ を最大にするような $(A',B')$ の組のうち, $A'=(1,2, \dots, N)$ となるものが存在する.

証明

何回かの隣接交換の結果 $(A', B')$ のうち, $\operatorname{LIS}(A')+\operatorname{LIS}(B')$ を最大にするようなものを取ってくる.

このとき, $A' \neq (1,2, \dots, N)$ ならば, $A'$ の最長増加部分列に寄与していない項 $A'_i$ が存在する. $A'_i, B'_i$ を適切な場所に移動させることによって, 操作後の列を $(A'', B'')$ としたとき, $\operatorname{LIS}(A'')=\operatorname{LIS}(A')+1$ とできる. また, $\operatorname{LIS}(A')+\operatorname{LIS}(B')$ が最大になるようにとってきたのだから, $\operatorname{LIS}(B'')=\operatorname{LIS}(B')-1$ である. よって, $\operatorname{LIS}(A'')+\operatorname{LIS}(B'')=\operatorname{LIS}(A')+\operatorname{LIS}(B')$ となり, これを繰り返していくことによって, $A=(1,2, \dots, N)$ にすることができる.

以上から, $A'=(1,2, \dots, N)$ のときに最大値になるような操作後の組 $(A', B')$ が存在し, この $B'$ は一意に定まることから, 答えは $(1,2, \dots, N)$ の並び替え $C$ を $A$ を $(1,2, \dots, N)$ に並び替えた時の $B$ とすることによって,