AC题解

操作本质
我们可以交换两个位置上的数，当且仅当它们的按位与等于 X。
也就是说，两个数 a 和 b可以交换 ⟺(a&b)=X.

#include <bits/stdc++.h>
using namespace std;

const int MAXB = 18;                 // 2^18 = 262144 > 2e5
const int FULL = (1 << MAXB) - 1;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> p(n);
        for (int i = 0; i < n; ++i) {
            cin >> p[i];
        }

        // 位置映射：数字 a 所在的位置
        vector<int> pos(n);
        for (int i = 0; i < n; ++i) {
            pos[p[i]] = i;
        }

        // 计算 M0 = 所有错位数字的 (a & pos[a]) 的按位与
        int M0 = FULL;               // 初始全1
        bool has_fixed = false;     // 是否有错位
        for (int a = 0; a < n; ++a) {
            if (a != pos[a]) {
                has_fixed = true;
                M0 &= (a & pos[a]);
            }
        }
        if (!has_fixed) {
            cout << "0\n";
            continue;
        }
        if (M0 == 0) {
            cout << "0\n";
            continue;
        }

        // 预处理：每个数字的位掩码就是它本身
        // 时间戳数组，用于快速判断某个掩码是否存在
        vector<int> occ(1 << MAXB, 0);
        int cur_stamp = 0;

        // 从大到小枚举所有 X（M0 的子集）
        for (int X = FULL; X >= 0; --X) {
            if ((X & ~M0) != 0) continue;   // 必须是 M0 的子集
            if (X == 0) continue;           // M0 != 0 时 X 不可能为 0，但安全起见

            ++cur_stamp;
            // 收集所有包含 X 的数字的签名
            vector<int> masks;              // 出现的签名
            vector<int> sig(n, -1);        // 每个数字的签名（只记录包含X的）
            bool has_zero = false;          // 是否存在签名为 0 的数字
            for (int val = 0; val < n; ++val) {
                if ((val & X) == X) {
                    int s = val & (~X);
                    sig[val] = s;
                    if (occ[s] != cur_stamp) {
                        occ[s] = cur_stamp;
                        masks.push_back(s);
                    }
                    if (s == 0) has_zero = true;
                }
            }
            // 如果存在签名为 0 的数字，则全连通
            if (has_zero) {
                // 只需要检查所有非固定点是否都有签名（它们肯定有，因为包含X）
                bool ok = true;
                for (int a = 0; a < n; ++a) {
                    if (a != pos[a]) {
                        // 非固定点一定包含 X，因为 X⊆M0 ⊆ (a&pos[a])，所以 sig 非空
                        if (sig[a] == -1) { ok = false; break; }
                    }
                }
                if (ok) {
                    cout << X << '\n';
                    break;
                }
                continue;
            }

            // BFS 求连通分量
            vector<int> comp(1 << MAXB, -1);
            queue<int> q;
            int comp_id = 0;
            for (int s : masks) {
                if (comp[s] != -1) continue;
                comp[s] = comp_id;
                q.push(s);
                while (!q.empty()) {
                    int u = q.front(); q.pop();
                    int sup = (FULL ^ X) ^ u;   // 当前签名 u 的补集（仅考虑自由位）
                    // 枚举 sup 的所有子集
                    int sub = sup;
                    while (true) {
                        if (occ[sub] == cur_stamp && comp[sub] == -1) {
                            comp[sub] = comp_id;
                            q.push(sub);
                        }
                        if (sub == 0) break;
                        sub = (sub - 1) & sup;
                    }
                }
                ++comp_id;
            }

            // 检查所有非固定点
            bool ok = true;
            for (int a = 0; a < n; ++a) {
                if (a != pos[a]) {
                    if (sig[a] == -1 || sig[pos[a]] == -1) {
                        ok = false;
                        break;
                    }
                    if (comp[sig[a]] != comp[sig[pos[a]]]) {
                        ok = false;
                        break;
                    }
                }
            }
            if (ok) {
                cout << X << '\n';
                break;
            }
        }
    }
    return 0;
}