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}
result: 0

先頭から見て、それまでの最大値を更新する要素を数える。
4 と 5 が該当するので、result=2 となる。
また、この $2$ 要素を n+1=6 に書き換える。

p: {6, 3, 1, 2, 6}
result: 2

末尾に n+1=6 を追加する。

p: {6, 3, 1, 2, 6, 6}

この配列の最長増加部分列の長さは $3$ である。
例えば、1, 2, 6 を選べる。
末尾に追加した 6 の分を除いた $2$ を result に加える。

result: 4

注意点

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

別解

特になし。