题解：P9139 [THUPC 2023 初赛] 喵了个喵 II

· · 题解

Blog

这或许是第一道我独立想出的黑题。

对每个元素观察匹配上的位置。假设对于元素 x，其在序列中出现的位置分别为 1, 2, 3, 4，那么只可能有两种匹配方式：

注意，此处的 1, 2, 3, 4 仅代表元素的相对位置，而不代表它们具体在序列中的位置。

进一步考虑两种元素之间，什么样的匹配是不合法的。显然如果匹配间的连线是相互嵌套的关系，则一定是不合法的。形式化地，如果 1 \le i < j < k < p \le n，满足 a_i, a_p 匹配，a_j, a_k 匹配，那么就是不合法的。容易发现这个条件已经能判断方案的合法性了。

由于每个元素的状态可以用一个 01 变量进行刻画，而不合法的条件是一个二元限制，所以很容易想到用 2-SAT 算法来描述这个问题结构。如果 m \le 10^3，直接暴力建图即可。但是当 m \le 5\times 10^4 时，就必须使用一些手段来优化建图。

注意到这个建图的形式，是向一个区间的子区间进行连边，而子区间的条件刚好又可以放在二维平面上进行刻画，于是问题变为了二维偏序类的连边。可以直接使用主席树优化建图 + Tarjan 求强连通分量，得到一组合法的 2-SAT 解。时间复杂度 O(n\log n)。

但是主席树的时间空间常数都太大了，于是我们考虑使用 Kosaraju 算法求强连通分量。这个算法的好处在于，它并不需要显式地进行建图，而是只需要支持“寻找出边中所有未被访问到的节点”即可，这里可以直接使用朴素线段树进行维护。时间复杂度 O(n\log n)，但是空间复杂度变为 O(n)。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc (p << 1)
#define rc ((p << 1) | 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 2e5 + 10, inf = 0x3f3f3f3f;
int n, a[N], scc[N], scctot;
vector<int> pos[N], topo;
set<pi> Rpos[N];
pi ranges[N][2];
map<pi, int> MappL;

struct Node{
    int l, r;
    pi mx, mn;
};

struct Segtree{
    Node tr[4 * N];

    void pushup(Node &p, Node ls, Node rs) {
        p.mx = max(ls.mx, rs.mx);
        p.mn = min(ls.mn, rs.mn);
    }

    void build(int p, int ln, int rn) {
        tr[p] = {ln, rn, {-inf, -inf}, {inf, inf}};
        if(ln == rn) {
            Rpos[ln].clear();
            return;
        }
        int mid = (ln + rn) >> 1;
        build(lc, ln, mid);
        build(rc, mid + 1, rn);
        pushup(tr[p], tr[lc], tr[rc]);
    }

    void update(int p, int pos, pi rg, bool typ) {
        if(tr[p].l == tr[p].r) {
            if(typ == 0) Rpos[pos].erase(rg);
            else Rpos[pos].insert(rg);

            if(Rpos[pos].empty()) {
                tr[p].mn = {inf, inf};
                tr[p].mx = {-inf, -inf};
            }
            else {
                tr[p].mn = *Rpos[pos].begin();
                tr[p].mx = *Rpos[pos].rbegin();                
            }

            return;
        }
        int mid = (tr[p].l + tr[p].r) >> 1;
        if(pos <= mid) update(lc, pos, rg, typ);
        else update(rc, pos, rg, typ);

        pushup(tr[p], tr[lc], tr[rc]);
    }

    Node query(int p, int ln, int rn) {
        if(ln <= tr[p].l && tr[p].r <= rn) {
            return tr[p];
        }
        int mid = (tr[p].l + tr[p].r) >> 1;
        if(rn <= mid) return query(lc, ln, rn);
        if(ln >= mid + 1) return query(rc, ln, rn);
        Node res;
        pushup(res, query(lc, ln, rn), query(rc, ln, rn));
        return res;
    }
} tr1;

bitset<N> vis, ans;

void Kosaraju(int u, int typ) {
    vis[u] = 1;
    for(int i = 0; i <= 1; i++) {
        int l = ranges[u][i].fi, r = ranges[u][i].se;
        Node res = tr1.query(1, l + 1, r);
        while(res.mn.fi <= r) {
            int id = res.mn.se;
            int ql = MappL[res.mn];
            tr1.update(1, ql, res.mn, 0);
            if(!vis[id]) {
                Kosaraju(id, typ);
            }
            res = tr1.query(1, l + 1, r);
        }

        res = tr1.query(1, 1, l);
        while(res.mx.fi > r) {
            int id = res.mx.se;
            int ql = MappL[res.mx];
            tr1.update(1, ql, res.mx, 0);
            if(!vis[id]) {
                Kosaraju(id, typ);
            }
            res = tr1.query(1, 1, l);
        }
    }
    if(typ == 0) {
        topo.push_back(u);
    }
    else {
        scc[u] = scctot;
    }
}

int main()
{
    // freopen("P9139.in", "r", stdin);
    // freopen("P9139.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= 4 * n; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }

    // DFS 1
    tr1.build(1, 1, 4 * n);
    for(int i = 1; i <= n; i++) {
        int p1 = pos[i][0], p2 = pos[i][1], p3 = pos[i][2], p4 = pos[i][3];
        tr1.update(1, p1, {p3, i + n}, 1);
        tr1.update(1, p2, {p4, i + n}, 1);
        ranges[i][0] = {p1, p3};
        ranges[i][1] = {p2, p4};
        MappL[{p3, i + n}] = p1;
        MappL[{p4, i + n}] = p2;

        tr1.update(1, p1, {p2, i}, 1);
        tr1.update(1, p3, {p4, i}, 1);    
        ranges[i + n][0] = {p1, p2};
        ranges[i + n][1] = {p3, p4};    
        MappL[{p2, i}] = p1;
        MappL[{p4, i}] = p3;
    }

    for(int i = 1; i <= 2 * n; i++) {
        if(!vis[i]) {
            Kosaraju(i, 0);
        }
    }

    // DFS2
    vis.reset();
    tr1.build(1, 1, 4 * n);
    for(int i = 1; i <= n; i++) {
        int p1 = pos[i][0], p2 = pos[i][1], p3 = pos[i][2], p4 = pos[i][3];
        tr1.update(1, p1, {p3, i}, 1);
        tr1.update(1, p2, {p4, i}, 1);
        ranges[i][0] = {p1, p2};
        ranges[i][1] = {p3, p4};
        MappL[{p3, i}] = p1;
        MappL[{p4, i}] = p2;

        tr1.update(1, p1, {p2, i + n}, 1);
        tr1.update(1, p3, {p4, i + n}, 1);    
        ranges[i + n][0] = {p1, p3};
        ranges[i + n][1] = {p2, p4};
        MappL[{p2, i + n}] = p1;
        MappL[{p4, i + n}] = p3;
    }
    for(int i = topo.size() - 1; i >= 0; i--) {
        int u = topo[i];
        if(!vis[u]) {
            ++scctot;
            Kosaraju(u, 1);
        }
    }

    for(int i = 1; i <= n; i++) {
        if(scc[i] == scc[i + n]) {
            cout << "No\n";
            return 0;
        }
        int p1 = pos[i][0], p2 = pos[i][1], p3 = pos[i][2], p4 = pos[i][3];
        if(scc[i] > scc[i + n]) {
            ans[p1] = ans[p2] = 1;
        }
        else {
            ans[p1] = ans[p3] = 1;
        }
    }

    cout << "Yes\n";
    for(int i = 1; i <= 4 * n; i++) {
        cout << ans[i];
    }
    return 0;
}