ABC-468-F - Chmax（观察到每步操作都要做只能够说有的时候不生效，然后就可以发现，有的是数字，我们是必须去取的）

题目大意

题目描述

给定正整数 $N$ 和 $(1,2,\ldots,N)$ 的一个排列 $P=(P_1,P_2,\ldots,P_N)$。

有三个变量 $x,y,c$，初始时 $x=y=c=0$。

你需要按 $k=1,2,\ldots,N$ 的顺序，依次执行下列两种操作之一：

• 操作 $1$：若 $x < P_k$，则将 $c$ 增加 $1$；随后将 $x$ 替换为 $\max(x,P_k)$。

• 操作 $2$：若 $y < P_k$，则将 $c$ 增加 $1$；随后将 $y$ 替换为 $\max(y,P_k)$。

求最终 $c$ 的最大可能值。

输入格式

输入从标准输入以如下格式给出：

$$N$$

$$P_1\ P_2\ \ldots\ P_N$$

输出格式

输出一行一个整数，表示答案。

数据范围

• $1\le N\le 5\times 10^5$

• $P$ 是 $(1,2,\ldots,N)$ 的一个排列

• 输入的所有值均为整数

样例

5
4 3 1 2 5

4

按如下方式操作可以达到 $c=4$：

• $k=1$ 时：执行操作 $1$，此时 $(x,y,c)=(4,0,1)$。

• $k=2$ 时：执行操作 $1$，此时 $(x,y,c)=(4,0,1)$。

• $k=3$ 时：执行操作 $2$，此时 $(x,y,c)=(4,1,2)$。

• $k=4$ 时：执行操作 $2$，此时 $(x,y,c)=(4,2,3)$。

• $k=5$ 时：执行操作 $2$，此时 $(x,y,c)=(4,5,4)$。

无论如何操作都无法使 $c$ 超过 $4$，因此输出 $4$。

6
6 5 4 3 2 1

2

9
3 6 5 2 7 8 9 1 4

7

思路讲解

我们不难注意到，这个前缀最大值数组中出现的值，我们必须要选啊，而且不仅仅是必须要选，我们的有一个 X / Y 的上升序列一定就是长这个样！否则就不是很优秀啊。

AC代码

源代码

心路历程（WA，TLE，MLE……）