UOJ174 新年的破栈题解

题意：

在这新年的第一天，神族首领 cxy 自然是要接受来自宇宙各国的朝贡的。在种类繁多的礼品中， q779 送来的栈引起了她的注意——她发现这个栈的大小正好适合来装她的核弹。

神族首领 cxy 有 $n$ 个核弹，编号为 $i$ 的核弹的威力是 $A_i$，而且任意两颗核弹的威力都是不同的。现在她想用这个栈来整理这些核弹，每时每刻她可以进行下面三种操作中的一种：

入栈：如果当前还有核弹没有被放入过栈中，那么就把剩下的核弹中编号最小的放到栈中（作为新的栈顶）。

出栈：如果当前栈中有核弹，那么就把栈顶（即栈中最后被放入的）的核弹取出来。

打开阀门：如果当前栈中有核弹，那么就把栈底（即栈中最先被放入的）的核弹取出来。

在所有核弹都从栈中取出后， cxy 按照核弹出栈的时间顺序排成一排，再把这些核弹的威力记录下来，这样就得到了一个数列 $B$。现在 cxy 想让这个数列的字典序尽可能的小，但是因为她日理万机，没有时间来想这种简单的小问题，于是她就让你来帮她求出字典序最小的数列 $B$。

对于两个长度为 $n$ 的数列 $a$ 和 $b$，$a$ 的字典序小于 $b$ 当且仅当存在一个整数 $k \in [1,n]$ 满足 $a_{i} = b_{i}(1 \leq i < k)$ 且 $a_k < b_k$。

输入格式：

第一行一个正整数 $T$，表示数据组数。

对于每组数据，第一行包含一个正整数 $n$。

接下来一行 $n$ 个正整数 $A_1, \dots, A_n$。

输出格式：

对于每组数据，输出一行 $n$ 个正整数，表示字典序最小的数列 $B$ 。

数据范围：

对于所有数据，保证 $1 \leq T \leq 5,~1\le n \le 10^5 ,~1 \leq A_i \leq 10^9$ 。

模拟了一会发现这东西貌似可以贪心。~~结果推了几组全是1开头的然后假了~~

首先可以发现，无论顺序是怎样的， $A_0$ 一定在答案的第一项（ $A_0 = \min{A_i}$）。

因为只需要不停地入栈直到遇到 $A_0$ ，然后把 $A_0$ 弹出，总能得到第一项为 $A_0$ 的答案。

考虑第二项，它一定是以下三种情况的最小值：

选择此时的栈顶元素
选择此时的栈底元素
继续入栈，直到遇到一个极小值。

可以发现重复这个过程就能找到答案。

考虑如何实现。首先这个栈其实就是个双端队列，直接维护即可。

然后这个极小值其实就是后缀最小值，可以预处理出来。其他直接模拟即可

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,st,en,a[N],mn[N],q[N];
void solve()
{
    cin >> n; mn[n+1] = INF; st=en=0;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=n; i; i--) mn[i] = min(a[i], mn[i+1]);
    for(int i=1,j=1; i<=n; i++)
        if(st < en && (q[st+1] < mn[j] || q[en] < mn[j]))
        { cout << (q[st+1] < q[en] ? q[++st] : q[en--]) << " \n"[i==n]; }
        else
        {
            cout << mn[j] << " \n"[i==n];
            for(; a[j] != mn[j]; j++) q[++en] = a[j]; ++j;
        }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}