题解 P1750 【出栈序列】

· · 题解

原题解锅了，这里整个重写一遍。

以下内容写于 2022 年 8 月 5 日。

论还有半个月就退役的我在这里水黄题。

三年前还是普及组选手的我做过这题，当时看不懂题解，自己整了个线性做法，然而没有正确性证明。

三年后这篇题解成为了我赞最多的博客，然而我发现它锅了。并且我毫不意外地还是看不懂其他题解。

现在我们来修这个锅。

下面令 m 表示题面里的 c。

我们有两种操作：入栈和出栈。入栈这个操作会对栈产生影响，但不会对结果序列产生影响，这很不利于我们的分析。

我们希望每一步都能使结果序列后面多一个数，那么我们把两种操作改成：

这和原来的两种操作是等价的。

执行第二种操作时，我们要入栈多少个数呢？由于我们要最小化的的是字典序，所以我们肯定贪心地想要让入栈的最后一个数，即出栈的那个数最小。

令 l 为 a 中第一个还没有被入栈的数的位置，r 表示我们最多可以一次性入栈 r-l+1 个数，也就是说最多可以把下标在 [l,r] 中的所有数都入栈。如果当前栈中有 s 个元素，我们可以算出 r=\min\{l+m-s-1,n\}。

那么，如果我们这一步入栈 x-l+1 个数，再出栈一个数即 a_x，我们想要 a_x 是 a_l 到 a_r 中最小的数。这样我们就可以知道，这一步如果执行第二种操作，需要连续入栈多少个数了。

比较严谨的小朋友就要问了，最小的 a_x 可能不止一个呀？等会我们再讨论这个问题。

但是，有两种操作，我们应该执行哪一个呢？不难发现，我们应该比较 a_x 和当前的栈顶元素。如果 a_x 更小，则执行第二种操作，否则执行第一种操作。

严谨的小朋友又要问了，如果两个数相等呢？我们还是等会再来讨论这个问题。

可能光说比较难以理解，我们来手玩一下样例：

6 3
5 2 3 8 7 4
  1. 当前栈为空，l=1，r=3，x=2。执行第二种操作，入栈两个数再出栈一个数即 a_x=2。
  2. 当前栈为 [5]，l=3，r=4，x=3。由于 a_x=3 小于栈顶 5，执行第二种操作，入栈一个数再出栈一个数 3。
  3. 当前栈为 [5]，l=4，r=5，x=5。由于 a_x=7 大于栈顶 5，执行第一种操作，出栈一个数 5。
  4. 当前栈为空，l=4，r=6，x=6。执行第二种操作，入栈三个数再出栈一个数 4。
  5. 当前栈为 [8,7]（右边是栈顶），l=7（用 l>n 表示原序列中没有数没有被入栈了），r=6。执行第一种操作，出栈一个数 7。
  6. 当前栈为 [8]，执行第一种操作，出栈一个数 8。

最终得到的结果序列是 [2,3,5,4,7,8]，跟样例输出是一样的。

如果没有相同的元素，问题就已经被解决了。真可惜，我们还得回过头来讨论上面提出的两种相等的情况。

如果最小元素不止一个？

猜测一下，我们选择最左边的那个。但是为什么呢？

考虑利用反证法证明这个结论：假设有两个数 x 和 y 满足 l\le x<y\le r，a_x=a_y，我们假设选 y 可以得到更优的结果。那么，我们开辟一条新的世界线，考虑在这个世界线里选择 x 并进行一次操作二。

接着，我们把下标 [x+1,y] 的数全部入栈（不出栈）。这样，我们的情况相比于原世界线执行完这次操作二之后的情况，只是栈里的 a_x 跨越了一些不小于它的数跑到了栈顶。

这种情况显然是不劣于原世界线的。因为，我们之后可以对原世界线的每一次操作，都在新世界线里执行一样的操作。容易证明结果序列不劣于原来的世界线。

于是我们导出了假设的矛盾！根据反证法，我们可以证明结论，即我们应该选择左边的 x 而非右边的 y。

如果 a_x 等于栈顶元素？

那么我们断言直接进行出栈操作是不劣的。证明和上面几乎一样，留给读者作练习。

下面的话留给普及组选手：

如果你不会证明，你可以手玩一些数据来猜测并验证结论。比如下面两个数据就对应了上面两种情况。

3 3
1 2 1
4 3
2 1 3 2

但是！不要觉得这样证明就没有用了。你可能听说过“OIer 不需要证明”的说法，但是这种想法是绝对错误的。

不是所有结论都可以手玩或者感性理解，凭借直觉去猜结论经常会猜错。所以一定要养成多问证明的好习惯，即使在考场上你可能不会严谨证明每个结论。

……好吧，其实我是一个直觉很差的选手，而且每个结论我都需要一个严谨到每个字的证明。这对我平时做题和考试都造成了不小的负面影响。所以可能我是错的，我这种傻逼的建议听听就好。

等等！我们怎么找到这个 x 呢？当然可以暴力或者使用 std::multiset 进行优化，得到 O(n^2) 或者 O(n\log n) 的时间复杂度并通过此题。但是，不是说有线性做法吗？

可以证明，l 和 r 都是单调不减的。这样左右端点都只会往一个方向移动的区间，我们称之为滑动窗口。我们要做的就是维护这个窗口内最靠左的最小值。

我们使用单调队列线性解决这个问题。这里有一道模板题，也可以去看看这题的题解。如果你已经会了这个数据结构，你可以跳过这一段。

单调队列基于这样一个事实：如果有两个位置 x 和 y，满足 x<y 且 a_x>a_y，那 a_x 就永远没用了。因为 a_y 会更晚从窗口里被移出去，而且还更小。

我们用一个双端队列维护窗口内所有有用的数，队列里从队头到队尾下标递增，那么值是不降的。每次我们要移动窗口的左端点时，就把队头的一些元素出队。

而我们要移动右端点时，就入队一些元素。每次入队会使队尾的一些元素变得没用，要在入队之前把它们从队列里移出去。

这样，队头就是当前窗口内最靠左的最小值。那么这个做法的时间复杂度是多少呢？每个元素只会入队一次，出队一次，所以是 O(n) 的。

那么我们在线性时间内完整解决了整个问题。由于输入就需要这么多时间，我们做到了理论最优的时间复杂度。

这里把单调队列讲一遍纯粹是因为原来写的题解讲了一遍。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
inline ll read(){
    ll x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=1e4+5;
int n,m,a[maxn],q[maxn],hd=1,tl=0;
int main(){
#ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    n=read();
    m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++){
        while(hd<=tl&&a[i]<a[q[tl]]) tl--;
        // 必须是 a[i]<a[q[tl]] 而不是 <=
        q[++tl]=i;
    }// 入队最开始 m 个元素
    int l=1,r=m;
    vector<int> s;// 栈
    for(int i=1;i<=n;i++){
        if(hd<=tl&&(!s.size()||a[q[hd]]<s.back()))
        // 比较两种操作，必须是 < 而不是 <=
            while(l<=q[hd]) s.push_back(a[l++]);
        // 入栈一堆元素
        printf("%d ",s.back());
        s.pop_back();// 出栈并输出
        while(r<n&&r<l+m-(int)s.size()-1){// 移动 r
            r++;
            while(hd<=tl&&a[r]<a[q[tl]]) tl--;
            q[++tl]=r;// 入队
        }
        while(hd<=tl&&q[hd]<l) hd++;// 移动 l，出队
    }
#ifdef LOCAL
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
#endif
    return 0;
}

以下是碎碎念。

事情是这样的。这篇题解被 hack 了，我发现好像在有相等元素时会寄。想了一下修好了，但是不太可能直接在原有题解上修，于是决定重写。

很久没有写黄题的题解了，我也不知道普及组选手喜欢什么样的。太简略的题解肯定是看不懂的，但是我当时好像也嫌弃一些题解总是啰里吧嗦讲一大堆有的没的。但是没办法，只能按怎么详细怎么来了。

这应该是我博客里现有的最早的文章，也是赞最多的一篇。我会认真对待它，希望对你有帮助。

莫名其妙写了这么长，比我很多黑题的题解都长多了。就到这里吧。