P14162 [ICPC 2022 Nanjing R] 完美匹配 题解

// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
const int N = 1000010;
const int inf = 1e18;
const int mod = 998244353;

int a[N], b[N], l[N], r[N], vis[N], dep[N], buc[N];
vector<pair<int, int>> adj[N];
struct DSU
{
    int fa[N], siz[N];
    inline DSU() { iota(fa, fa + N, 0), fill(siz, siz + N, 1); }
    inline void init(int _) { iota(fa, fa + _ + 1, 0), fill(siz + 1, siz + _ + 1, 1); }
    inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
    inline int merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x != y)
            return fa[x] = y, 1;
        return 0;
    }
} dsu;

vector<pair<int, int>> res;
inline int dfs(int u, int fa, int frt, int dp)
{
    vector<int> vv;
    dep[u] = dp, vis[u] = 1;
    for (auto &[v, id] : adj[u])
        if (v != fa)
        {
            if (dep[v])
            {
                if (dep[v] < dep[u])
                    vv.emplace_back(id);
            }
            else
            {
                int o = dfs(v, u, id, dp + 1);
                if (~o)
                    vv.emplace_back(o);
            }
        }
    for (int i = 0; i + 1 < vv.size(); i += 2)
        res.emplace_back(vv[i], vv[i + 1]);
    if (vv.size() & 1)
    {
        // assert(~frt);
        // cerr << "wtf " << u << ' ' << fa << ' ' << frt << ' ' << dp << ' ' << vv.size() << '\n';
        res.emplace_back(vv.back(), frt);
        return -1;
    }
    return frt;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        int _ = 0;
        for (int i = 1; i <= n; ++i)
            b[++_] = a[i] - i;
        sort(b + 1, b + _ + 1);
        _ = unique(b + 1, b + _ + 1) - b - 1;
        for (int i = 1; i <= n; ++i)
            l[i] = lower_bound(b + 1, b + _ + 1, a[i] - i) - b;
        int __ = 0;
        for (int i = 1; i <= n; ++i)
            b[++__] = a[i] + i;
        sort(b + 1, b + __ + 1);
        __ = unique(b + 1, b + __ + 1) - b - 1;
        for (int i = 1; i <= n; ++i)
            r[i] = lower_bound(b + 1, b + __ + 1, a[i] + i) - b + _;
        for_each(adj, adj + n + n + 5, [&](auto &o) { o.clear(); });
        fill(vis, vis + n + n + 5, 0), fill(dep, dep + n + n + 5, 0);
        int ok = 1;
        dsu.init(n + n + 4);
        for (int i = 1; i <= n; ++i)
        {
            adj[l[i]].emplace_back(r[i], i);
            adj[r[i]].emplace_back(l[i], i);
            dsu.merge(l[i], r[i]);
            // cerr << "ae " << l[i] << ' ' << r[i] << ' ' << i << '\n';
        }
        fill(buc + 1, buc + n + n + 5, 0);
        int cnt = 0;
        for (int i = 1; i <= n; ++i)
            if (dsu.find(l[i]) == dsu.find(r[i]))
                ++buc[dsu.find(l[i])];
        for (int i = 1; i <= _ + __; ++i)
            if (buc[dsu.find(i)] & 1)
            {
                ok = 0;
                break;
            }
        if (ok)
        {
            res.clear();
            for (int i = 1; i <= _ + __; ++i)
                if (!vis[i])
                    /*cerr << "start from " << i << '\n', */dfs(i, 0, -1, 1);
            cout << "Yes\n";
            for (auto &[x, y] : res)
                cout << x << ' ' << y << '\n';
        }
        else
            cout << "No\n";
    }
    return 0;
}