思路与算法

若i<j且a_i<a_j，且j后仍有值小于a_i，则两元素不能入同一栈；建立冲突图并二染色。每个分量最早位置用栈1。模拟时优先可行a，再必须的b、c、d，输出字典序最小操作串。

正确性说明

冲突三元组迫使前两元素分栈，否则后续小值出来后会先弹较大的a_j而违背升序；这些冲突也是单栈内出现禁形的全部情况，因此二染色刻画可双栈排序性。每个可交换颜色分量的首个压栈选a最小；保持每栈下降并只弹当前应输出值，在不破坏可完成性的前提下按a<b<c<d选择，得到最小字典序。

复杂度

O(n²)时间、O(n²)空间，含后缀最小值、冲突图、染色、两个栈和输出数组初始化。

易错点

字典序比较的是整串操作，不能每次输入后立即弹出所有能弹的值；有时须继续压a。奇环输出0。独立小规模全状态字典序搜索验证构造与最小性。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> a(n), mn(n + 1, n + 1);
    for (int &x : a)
        cin >> x;
    for (int i = n - 1; i >= 0; i--)
        mn[i] = min(mn[i + 1], a[i]);
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] < a[j] && mn[j + 1] < a[i]) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
    vector<int> c(n, -1);
    for (int s = 0; s < n; s++)
        if (c[s] < 0) {
            c[s] = 0;
            vector<int> q(1, s);
            for (int i = 0; i < (int)q.size(); i++)
                for (int v : g[q[i]])
                    if (c[v] < 0) {
                        c[v] = 1 - c[q[i]];
                        q.push_back(v);
                    } else if (c[v] == c[q[i]]) {
                        cout << 0 << "\n";
                        return 0;
                    }
        }
    vector<int> st[2];
    vector<char> out;
    int want = 1;
    auto pop = [&]() {
        for (int t = 0; t < 2; t++)
            if (!st[t].empty() && st[t].back() == want) {
                st[t].pop_back();
                out.push_back(t ? 'd' : 'b');
                want++;
                return true;
            }
        return false;
    };
    for (int i = 0; i < n; i++) {
        int t = c[i];
        while (!st[t].empty() && st[t].back() < a[i])
            if (!pop()) {
                cout << 0 << "\n";
                return 0;
            }
        if (t)
            while (!st[0].empty() && st[0].back() == want)
                pop();
        st[t].push_back(a[i]);
        out.push_back(t ? 'c' : 'a');
    }
    while (want <= n)
        if (!pop()) {
            cout << 0 << "\n";
            return 0;
        }
    for (int i = 0; i < (int)out.size(); i++) {
        if (i)
            cout << ' ';
        cout << out[i];
    }
    cout << "\n";
}