ABC-468-F - Chmax(观察到每步操作都要做只能够说有的时候不生效,然后就可以发现,有的是数字,我们是必须去取的) · znzryb
## 题目大意
### 题目描述
给定正整数 $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)$ 的一个排列
- 输入的所有值均为整数
### 样例
<!-- Notion block type: heading_4 -->
```
5
4 3 1 2 5
```
<!-- Notion block type: heading_4 -->
```
4
```
<!-- Notion block type: heading_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$。
<!-- Notion block type: heading_4 -->
```
6
6 5 4 3 2 1
```
<!-- Notion block type: heading_4 -->
```
2
```
<!-- Notion block type: heading_4 -->
```
9
3 6 5 2 7 8 9 1 4
```
<!-- Notion block type: heading_4 -->
```
7
```
## 思路讲解

我们不难注意到,这个前缀最大值数组中出现的值,我们必须要选啊,而且不仅仅是必须要选,**我们的有一个 X / Y 的上升序列一定就是长这个样**!否则就不是很优秀啊。
## AC代码
::: 源代码
```cpp
```
:::
## 心路历程(WA,TLE,MLE……)