ABC468F Chmax

核心结论是：

删除所有“前缀最大值”，剩余序列记为 $Q$。
答案等于“前缀最大值个数”加上 $Q$ 的最长上升子序列长度。

官方题目给出的范围是 $N\le 5\times 10^5$，因此需要使用 $O(N\log N)$ 的做法。(AtCoder)

关键性质

处理完前 $i$ 个数后，一定有

$\max(x,y)=\max(P\_1,P\_2,\ldots,P\_i).$

因为每个 $P\_i$ 都会被放进 $x$ 或 $y$ 中。

1. 遇到新的前缀最大值

假设当前数字 $P\_i$ 比之前所有数字都大，那么它也一定大于当前的 $x$ 和 $y$。

所以无论选择哪一个操作，$c$ 都必然增加 $1$。

为了让后续更容易得分，应当把较大的变量更新成 $P\_i$，较小的变量保持不变。例如当前

$x=8,\quad y=3,\quad P\_i=10,$

就令 $x=10$，而不是令 $y=10$。这样较小值仍然是 $3$，后面更容易出现比它大的数。

因此，每个前缀最大值都固定贡献 $1$。

2. 遇到不是前缀最大值的数

设当前两个变量分别是

$M=\max(x,y),\qquad p=\min(x,y).$

因为 $P\_i$ 不是前缀最大值，所以

$P\_i\<M.$

此时有两种选择：

• 把 $P\_i$ 放入较大的变量 $M$：不会得分，状态也不变。
• 把 $P\_i$ 放入较小的变量 $p$：只有当 $P\_i>p$ 时才能得分，随后 $p$ 变成 $P\_i$。

因此，非前缀最大值想要得分，选出的数必须依次严格递增。

这正好就是最长上升子序列。

举例

样例：

$P=(4,3,1,2,5).$

前缀最大值是

$4,5,$

固定贡献 $2$。

删除它们后：

$Q=(3,1,2).$

$Q$ 的最长上升子序列可以选

$1,2,$

长度为 $2$。

所以答案为

$2+2=4.$

这个结论也是官方题解给出的进一步化简：答案为前缀最大值数量与删除这些元素后序列的 LIS 长度之和。(AtCoder)

C++14 代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    int mx = 0, ans = 0;
    vector<int> d;

    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        if(x > mx) {
            mx = x;
            ans++;
        } else {
            auto it = lower_bound(d.begin(), d.end(), x);

            if(it == d.end()) d.push_back(x);
            else *it = x;
        }
    }

    cout << ans + (int)d.size() << '\n';
    return 0;
}

其中 d[i] 表示长度为 $i+1$ 的上升子序列，其末尾元素的最小可能值。使用 lower_bound 维护严格上升子序列。

时间复杂度为

$O(N\log N),$

空间复杂度为

$O(N).$