ABC468 F - Chmax

考え方

最初の数は、$x$ と $y$ のどちらの更新に使っても話が全く同じである。
よって、最初に操作 $1$ を行い $x$ を更新したと仮定して話をする。

$x$ より大きい数が初めて来たときを考える。
このとき、条件から必ず $x>y$ になっており、どちらの操作をしても必ず値が更新される。
そのため、貪欲に $x$ の更新に使うと決めてよい。
なぜなら、$y$ の更新に使った後に可能なすべての操作は、$x$ の更新に使った場合でも可能だからである。
（$x$ と $y$ の立場が逆になるが、最終的な $c$ の値は同じである）

その次にまた $x$ より大きい数が来た場合も同様に、貪欲に $x$ の更新に使ってよい。
つまり、これまでで最大の数が来た場合、全て $x$ の更新に使うと決めてよい。
ということで、順列 $P$ の中の該当する個数をとりあえず結果に足し、該当する数を除去する。

残った数は、以下の $2$ つのいずれかに使える。

• $y$ の最大値を更新する
• $y$ の最大値を更新しない（$x$ にぶつけて失敗させる）

これの最大個数は、ただの最長増加部分列の問題である。
よって、その個数を結果に足すと、答えになる。

$x$ 更新に使われた数の除去は、以下のどちらでもよい。

• それらを除去した数列を改めて作る
• 除去する代わりに $n+1$ に書き換え、最後にも $n+1$ を書き足す（最長増加部分列長から $1$ を引く）

計算量は最長増加部分列の処理部分が支配的で、普通の方法なら $O(N \log N)$。

入力例1での動作

入力を受け取る。

n: 5
p: {4, 3, 1, 2, 5}

先頭から見て、それまでの最大値を更新する要素を確認する。

$4$ と $5$ の $2$ 個を $x$ の更新に使う。
この $2$ 要素を $n+1=6$ に書き換えると、次のようになる。

{6, 3, 1, 2, 6}

さらに末尾に $6$ を追加する。

{6, 3, 1, 2, 6, 6}

この配列の最長増加部分列の長さは $3$ である。
例えば、$1,2,6$ を選べる。

最後の $6$ は追加した番兵の分なので、残った数から $y$ の更新に使えるのは $3-1=2$ 個である。
したがって、最大値を更新できる回数は $2+2=4$ 回となる。

注意点

好きな単調増加列を $2$ つ取ることはできない。
例えば、 5 3 4 1 2 の答えは $4$ ではなく $3$ である。
先頭の $5$ に対して、「使わない」という選択は許されていない。

別解

特になし。