题目大意

初始有一个空序列，现对于这个序列做若干操作。操作有两种类型：

• $add$操作：在序列末尾加上一个非负整数 $x$

• $back$操作：给出$x$，回到现有的第$x$次$add$操作之后的版本，并且将第$x$次$add$操作之后的版本全部删除。

给出$n$，表示操作的总次数，请在每一次操作后，输出当前版本序列的最长不降子序列的长度。

对于全部测试点，保证$n\leq 5\times 10^5,x_i \le 10^7$，且对于每一次$back$操作有$x_i \le$ 当前序列长度。

思路

首先我们可以分析单纯的 $add$ 操作的做法。也就是 $O(n\log_2 n)$ 的时间复杂度。比较简单不在复述。之后我们考虑加上第二个操作。

首先我们用一个use变量来代表当前是第几个 $add$ 操作。之后，如果有一个 $back$ 肯定就是让use 回到 $x$ 了。然后考虑怎么弄值。我们如果开一个数组 $ans$，$ans[i]$ 为在第 $i$ 个 $add$ 操作时的答案。那么每一次只要输出 $ans[use]$ 即可。但是有一个很头疼的是将第$x$次$add$操作之后的版本全部删除。那我们考虑一下怎么实现。首先删除操作就正常遍历所有大于 $x$ 的 $add$ 操作。之后，如果不删除的话就可能会出现用二分的那个 $dp$ 最优值不存在了。那么直接更换为上一个没有被更换的值即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;
typedef long long ll;
const ll MAXN = 5e5 + 5;
ll use;
ll dp[MAXN];
ll ans[MAXN];
ll n;
stack<ll> add;
ll p[MAXN], Dp[MAXN];

int main() {
    scanf("%lld", &n);
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    while (n--) {
        ll op, x;
        scanf("%lld%lld", &op, &x);
        if (op == 0) {
            use++;
            add.push(use);
            ans[use] = ans[use - 1];
            if (x >= dp[ans[use]]) {
                dp[++ans[use]] = x;
                p[use] = ans[use];
                Dp[use] = 0x3f3f3f3f3f;
            } else {
                ll num = upper_bound(dp + 1, dp + ans[use], x) - dp;
                Dp[use] = dp[num];
                dp[num] = x;
                p[use] = num;
            }
        } else {
            while (!add.empty() && add.top() > x) {
                dp[p[add.top()]] = Dp[use];
                add.pop();
                use--;
            }
        }
        printf("%lld\n", ans[use]);
    }
    return 0;
}

总结

本题实际上是使用了迭代的方式去想题。首先想最基本的情况。然后不断添加元素使得问题一步一步变得复杂与接近原题。