算法

(二分图,栈,染色法,贪心) $O(n^2)$

如果只有一个栈，则整个操作顺序是固定的：

• 从前往后遍历每个数，每次先将当前数压入栈中，如果后面的所有数均比栈顶元素大，则将栈顶弹出，否则栈顶不能被弹出。

因此，我们只需考虑将每个数分配给哪个栈即可。

这里有个很强的性质：

两个数 $i, j(i \le j)$ 不能被放入同一个栈中，当且仅当存在 $k, k > j$, 且 $q[k] < q[i] < q[j]$。

证明：

必要性：
如果有 i < j < k, 且 q[k] < q[i] < q[j]，则因为 q[i] 和 q[j] 的后面均存在一个更小的q[k]，因此q[i]和q[j]都不能从栈中被弹出，所以从栈底到栈顶的元素就不是单调的降序了，那么弹出时得到的序列就会出现逆序对。因此q[i]和q[j]不能被分到同一个栈中。

充分性：
如果q[i]和q[j]不满足上述条件，则我们在操作过程中一定不会出现矛盾。

在操作过程中，如果当前要入栈的数是q[j]，那么此时：

• 所有大于q[j]的元素，都一定在栈中；
• 所有小于q[j]的元素，比如q[i] < q[j]，则由于后面不存在q[k] < q[i]，因此q[i]一定已经出栈；

所以此时将q[j]压入栈中后，从栈底到栈顶仍然可以保持降序，因此整个进栈、出栈过程是可以顺利进行的。

有了上述性质后，我们只需将所有满足条件的点分到两个栈中去即可。这一步可以转化成图论问题：

• 如果i, j满足条件，则在i和j之间连一条边。

然后判断是否是二分图即可。判断二分图可以用染色法，可以参考AcWing 860. 染色法判定二分图。

输出字典序最小的方案

答案要求字典序最小，因此从前往后染色时，需要优先将当前点分配到第一个栈中。

另外对于每一个栈，操作序列是唯一确定的，也就是'ab'的相对顺序是固定的，且'cd'的相对顺序也是固定的。
另外在最优解中，每个数插入哪个栈中也是唯一确定的，所以'ac'的相对顺序也固定。
最后，输出序列是唯一确定的，所以'bd'的相对顺序也固定。

所以在最终方案中，只有'ad'、'bc'的相对顺序可变，所以我们只需先随便求一个方案，然后将所有连续的bc区间排序，以及连续的ad区间排序即可。

时间复杂度

建图时需要枚举所有点对，时间复杂度是 $O(n^2)$。
染色法判定二分图的时间复杂度是 $O(n + m)$。
最后模拟栈排序的过程需要 $O(n)$ 的计算量。

因此总时间复杂度是 $O(n^2)$。

C++ 代码

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

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];
bool g[N][N];
int color[N];

bool dfs(int u, int c)
{
    color[u] = c;
    for (int j = 1; j <= n; j ++ )
    {
        if (!g[u][j]) continue;
        if (color[j])
        {
            if (color[j] == c) return false;
        }
        else if (!dfs(j, 3 - c)) return false;
    }
    return true;
}

bool check(char a, char b)
{
    if (a == b) return true;
    if (a > b) swap(a, b);
    return a == 'b' && b == 'c' || a == 'a' && b == 'd';
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    f[n + 1] = n + 1;
    for (int i = n; i; i -- ) f[i] = min(a[i], f[i + 1]);

    for (int i = 1; i <= n; i ++ )
        for (int j = i + 1; j <= n; j ++ )
            if (a[i] < a[j] && f[j + 1] < a[i])
                g[i][j] = g[j][i] = true;

    for (int i = 1; i <= n; i ++ )
        if (!color[i] && !dfs(i, 1))
        {
            puts("0");
            return 0;
        }

    string res;
    stack<int> stk1, stk2;
    for (int i = 1, cur = 1; i <= n; i ++ )
    {
        if (color[i] == 1) stk1.push(a[i]), res += 'a';
        else stk2.push(a[i]), res += 'c';

        while (stk1.size() && stk1.top() == cur || stk2.size() && stk2.top() == cur)
        {
            if (stk1.size() && stk1.top() == cur) stk1.pop(), cur ++, res += 'b';
            else stk2.pop(), cur ++, res += 'd';
        }
    }

    for (int i = 0; i < res.size();)
    {
        int j = i + 1;
        while (j < res.size() && check(res[i], res[j])) j ++ ;
        sort(res.begin() + i, res.begin() + j);
        i = j;
    }

    for (auto c: res)
        printf("%c ", c);
    return 0;
}