CSES 2402：Two Stacks Sorting

CSES 2402：Two Stacks Sorting

題目大意：給你一個 $1\sim n$ 的排序 $a_1\sim a_n$，你有兩個 $\text{stack}$，你可以將 $a_i\ \text{push}$ 到其中一個 $\text{stack}$ 上面，或是將其中一個 $\text{stack}$ 頂端的元素 $\text{pop}$ 掉，加入到答案的尾端，最後想要答案為 $1\sim n$，請問是否可行，若可以，第 $i$ 個數字請輸出 $a_i$ 被 $\text{push}$ 到哪個 $\text{stack}$。

解法：如果只有一個 $\text{stack}$ 的情況，怎樣才不能成功呢？可以知道若 $i<j<k, a_k < a_i < a_j$ 就無法成功，且若無法成功，一定存在一組 $i<j<k, a_k < a_i < a_j$。首先如果有 $a_k < a_i < a_j$，因為 $a_k$ 比較小，在 $\text{pop}$ 之前 $a_i, a_j$ 都不能被 $\text{pop}$，可是 $a_i < a_j$，代表 $a_i$ 要在 $a_j$ 被加入之前就 $\text{pop}$ 掉，於是會矛盾；而如果不存在 $a_k < a_i < a_j$，就一定能成功，因為當 $a_j$ 要被加入時，所有 $<a_i$ 的數字在 $a_j$ 之後都不會出現，代表 $a_i$ 在 $a_j$ 進入之前就被 $\text{pop}$ 掉了，$a_j$ 就可以進入 $\text{stack}$。

先考慮一個 $O(n^2)$ 的作法：枚舉 $i, j(i<j, a_i < a_j)$，看 $a_j$ 之後有沒有數字 $<a_i$，若有，代表 $a_i, a_j$ 不能在同一個 $\text{stack}$，那就在 $a_i, a_j$ 間建一條邊，之後可以二分圖著色，若可以著色，代表有解，否則不行。可以令 $mn_i$ 代表 $a_i\sim a_n$ 的最小值，這樣枚舉加上著色的複雜度就是 $O(n^2)$。著色是其中一種作法，但是因為最多可能加 $O(n^2)$ 條邊，我們現在用另外一種並查集的作法，就是如果 $a_i, a_j$ 不能在同一個 $\text{stack}$，那就把 $a_i, \text{not}\ a_j$ 所在的集合合併，把 $a_j, \text{not}\ a_i$ 所在的集合合併，之後若 $a_i, \text{not}\ a_i$ 在同一個集合，那就代表不行。

現在我們要來優化複雜度，我們可以令 $L = mn_{i + 1} + 1, R = a_i - 1$，那輪到 $a_i$ 時，事實上就是把範圍在 $L\sim R$，且之前出現過的數字做並查集的操作，且可以知道最後會把 $L\sim R$ 的所有集合變成一個集合，這樣總複雜度就會是 $O(n\times\log(n))$。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;
const int INF = 2e9;

int n;
int a[SIZE], mn[SIZE], ans[2 * SIZE];
int to[2 * SIZE], h[2 * SIZE];
set<int> num;
set<tuple<int, int, int>> s;

int dsu (int x) {
    return x == to[x] ? x : (to[x] = dsu (to[x]));
}

void Merge (int a, int b) {
    a = dsu (a), b = dsu (b);
    if (a == b) return;
    if (h[a] < h[b]) swap (a, b);
    to[b] = a;
    h[a] += h[a] == h[b];
}

int opp (int x) {
    return x <= n ? x + n : x - n;
}

void solve() {
    cin >> n;
    FOR (i, 1, n) cin >> a[i];
    iota (to, to + 2 * n + 1, 0);
    mn[n + 1] = INF;
    for (int i = n; i >= 1; i--) mn[i] = min (mn[i + 1], a[i]);
    FOR (i, 1, n) {
        int L = mn[i + 1] + 1, R = a[i] - 1;
        vector<tuple<int, int, int>> tmp;
        int ll = INF, rr = 0, gg;
        if (L <= R) {
            for (auto it = s.lower_bound ({L, 0, 0}); it != s.end(); it++) {
                auto [r, l, g] = *it;
                if (l > R) break;
                auto lit = num.lower_bound (max (L, l));
                if (lit == num.end() || *lit > min (R, r)) break;
                Merge (g, opp (a[i]));
                Merge (opp (g), a[i]);
                tmp.pb (*it);
                ll = min (ll, l);
                rr = max (rr, r);
                gg = g;
            }
        }
        if (tmp.size()) {
            for (auto t : tmp) s.erase (t);
            s.insert ({rr, ll, dsu (gg)});
        }
        auto it = s.lower_bound ({a[i], 0, 0});
        if (it == s.end() || get<1> (*it) > a[i]) s.insert ({a[i], a[i], a[i]});
        else {
            auto [r, l, g] = *it;
            s.erase (it);
            if (l < a[i]) {
                auto it = prev (num.lower_bound (a[i]));
                s.insert ({*it, l, g});
            }
            s.insert ({a[i], a[i], a[i]});
            if (r > a[i]) {
                auto it = num.upper_bound (a[i]);
                s.insert ({r, *it, g});
            }
        }
        num.insert (a[i]);
    }
    FOR (i, 1, n) if (dsu (i) == dsu (i + n)) {
        cout << "IMPOSSIBLE\n";
        return;
    }
    FOR (i, 1, n) {
        if (!ans[dsu (a[i])]) {
            int k = ans[dsu (a[i] + n)];
            if (k != 1) ans[dsu (a[i])] = 1;
            else ans[dsu (a[i])] = 2;
            ans[dsu (a[i] + n)] = 3 - ans[dsu (a[i])];
        }
        cout << ans[dsu (a[i])] << " \n"[i == n];
    }
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！