问题重述

将 $2n$ 个位置编号 $1..2n$，初始配对为 $(2i-1,2i)$。
“交换 $i$ 与 $i+n$” 意味着：对于每个 $i=1..n$，我们可以独立决定是否交换位置 $i$ 与 $i+n$ 上的骑士。
因此每个原始对 $\{i,\,i+n\}$ 有一个布尔变量 $x_i\in\{0,1\}$（$0$ 表示不交换，$1$ 表示交换），最终位置 $p$ 上的骑士为：

• 若 $p\le n$：当 $x_p=0$ 时为 $a_p$，否则为 $a_{p+n}$；
• 若 $p>n$：当 $x_{p-n}=0$ 时为 $a_p$，否则为 $a_{p-n}$。

每张桌子 $k$ 包含位置 $2k-1$ 和 $2k$，因此 $S_k$ 由 $x_{L_k}$ 和 $x_{R_k}$ 决定，其中

$$L_k = ((2k-2)\bmod n)+1,\quad R_k = ((2k-1)\bmod n)+1. $$

每个原始对 $i$ 恰好在两张桌子中出现（一次作为 $L_k$，一次作为 $R_k$），而每张桌子恰好关联两个不同的原始对（$n>1$ 时）。
于是问题转化为：选定每个 $x_i$，使得 $S_1,\dots,S_n$ 的最大值与最小值之差最小。

可行性判定

固定一个区间 $[L,R]$，判断是否存在赋值 $\{x_i\}$ 使所有 $S_k\in[L,R]$。
对于桌子 $k$，其两个关联变量为 $u=L_k,\;v=R_k$。枚举 $x_u,x_v\in\{0,1\}$ 可得到四种可能的和值。
定义 $2\times 2$ 布尔矩阵 $M_k$：

$$M_k[x_u][x_v] = \begin{cases}1,& S_k(x_u,x_v)\in[L,R]\\0,&\text{otherwise}\end{cases} $$

$M_k$ 的行对应 $x_u$，列对应 $x_v$。

所有原始对作为变量，所有桌子作为约束，构成一个二分图：每个变量恰连接两个约束，每个约束恰连接两个变量。图由若干个偶环组成。
对于每个环，沿环将约束矩阵按顺序相乘（适当使用转置），得到乘积矩阵 $P$。环上存在可行赋值当且仅当 $P$ 的对角线上至少有一个 $1$。
因此全局可行当且仅当每个环的乘积矩阵都有非零迹。

最小化差值

所有可能的 $S_k$ 值共有 $4n$ 个（可能重复），将它们排序去重得到数组 $v[0..M-1]$。
我们要找最小的 $v[r]-v[l]$ 使得区间 $[v[l],v[r]]$ 可行。
随着 $L$ 增大或 $R$ 减小，可行性单调变差，因此可以使用双指针：

• 初始所有矩阵全 $0$（区间为空），所有环不可行。
• 左指针 $l$ 从 $0$ 到 $M-1$ 遍历，右指针 $r$ 从 $-1$ 开始单调递增。
• 对每个 $l$，不断增大 $r$，启用 $v[r]$ 对应的所有 $(k,x_u,x_v)$（将 $M_k[x_u][x_v]$ 置 $1$），直到所有环都可行。
• 此时记录 $v[r]-v[l]$ 更新答案。
• 然后禁用 $v[l]$ 对应的所有 $(k,x_u,x_v)$（将相应位置置 $0$），并移动 $l$ 到 $l+1$。

启用/禁用一个矩阵元素会改变相应桌子的 $M_k$，从而影响其所在环的乘积矩阵。我们需要快速维护每个环的乘积矩阵及其迹。

数据结构：线段树维护环的矩阵乘积

对每个环，将环上的桌子按顺序排列（顺序由遍历环的方向决定）。每个桌子在环中有一个方向（正向或反向），决定了叶子节点存储的是 $M_k$ 还是 $M_k^{\mathsf T}$。
为每个环建立一棵线段树，叶子节点存储当前 $2\times 2$ 布尔矩阵，内部节点存储子区间矩阵的布尔乘积。
启用/禁用一个矩阵元素时，更新对应桌子的 $M_k$，再更新该桌子所在环的线段树（单点更新），然后查询根节点的矩阵，检查其迹是否非零。
维护一个计数器记录当前不可行的环数，当计数器为 $0$ 时区间可行。

算法流程

1. 预处理

   • 读入 $n$ 和 $a[1..2n]$。若 $n=1$，直接输出 $0$。
   • 对每个桌子 $k=1..n$，计算 $L_k,R_k$ 以及四种组合的和值，记录到 value_to_entries 中。
   • 构建图：每个原始对 $i$ 关联两个桌子（一次作为 $L$，一次作为 $R$）。通过 DFS 找出所有环，确定环上桌子的顺序及方向。
   • 为每个环建立线段树，初始化所有叶子矩阵为全 $0$，根矩阵为全 $0$，计数器 = 环数。

2. 双指针扫描

   • 将 $4n$ 个和值排序去重得到 $v[0..M-1]$。
   • $l=0,\; r=-1,\; ans = \infty$。
   • 对于 $l$ 从 $0$ 到 $M-1$：
     • 当 $r+1<M$ 且计数器 $>0$ 时：
       • $r \leftarrow r+1$
       • 对 value_to_entries[v[r]] 中的每个 $(k,x_u,x_v)$，若 $M_k[x_u][x_v]$ 原来是 $0$，则置为 $1$，并更新线段树，若该环迹从 $0$ 变非 $0$ 则计数器减 $1$。
     • 如果计数器 $=0$：$ans = \min(ans,\; v[r]-v[l])$。
     • 否则（$r$ 已到 $M-1$ 仍不可行）：跳出循环。
     • 对 value_to_entries[v[l]] 中的每个 $(k,x_u,x_v)$，若 $M_k[x_u][x_v]$ 原来是 $1$，则置为 $0$，并更新线段树，若该环迹从非 $0$ 变 $0$ 则计数器加 $1$。
   • 输出 $ans$。

复杂度分析

• 每个和值被启用一次、禁用一次，总操作 $O(4n)$。
• 每次操作更新线段树，单次 $O(\log n)$（$n$ 为环长，总长 $n$）。
• 总复杂度 $O(n\log n)$，满足 $n$ 总和 $10^5$ 的限制。

实现细节

• $2\times2$ 布尔矩阵可用一个 $4$ 位整数表示，乘法可预计算或直接展开。
• 环的遍历：每个原始对 $i$ 记录两个邻接 (neighbor, desk, need_transpose)，用 vis 数组标记已访问的变量，从每个未访问变量出发沿边行走直到回到起点。
• 线段树：对每个环建立数组 tree[4*size]，每个元素为一个 $2\times2$ 矩阵（或整数）。单点更新时，叶子节点直接赋值，向上合并。
• 由于 $t$ 最大 $10^4$ 但 $n$ 总和 $10^5$，注意清空全局数组，避免内存泄漏。

参考代码

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

const int INF = 2e9;

struct Mat {
    bool a[2][2];
    Mat() { memset(a, 0, sizeof a); }
    Mat(bool b00, bool b01, bool b10, bool b11) {
        a[0][0] = b00; a[0][1] = b01;
        a[1][0] = b10; a[1][1] = b11;
    }
    bool trace() const { return a[0][0] || a[1][1]; }
};

Mat mul(const Mat &x, const Mat &y) {
    Mat z;
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            z.a[i][j] = (x.a[i][0] && y.a[0][j]) || (x.a[i][1] && y.a[1][j]);
    return z;
}

Mat transpose(const Mat &x) {
    return Mat(x.a[0][0], x.a[1][0], x.a[0][1], x.a[1][1]);
}

struct SegTree {
    int n;
    vector<Mat> t;
    SegTree(int sz = 0) : n(sz), t(4 * sz) {}
    void upd(int pos, const Mat &val, int v = 1, int l = 0, int r = -1) {
        if (r == -1) r = n - 1;
        if (l == r) {
            t[v] = val;
            return;
        }
        int m = (l + r) >> 1;
        if (pos <= m) upd(pos, val, v * 2, l, m);
        else upd(pos, val, v * 2 + 1, m + 1, r);
        t[v] = mul(t[v * 2 + 1], t[v * 2]);
    }
    Mat query() const { return t[1]; }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(2 * n);
    for (int i = 0; i < 2 * n; ++i) cin >> a[i];
    if (n == 1) {
        cout << 0 << '\n';
        return;
    }

    vector<int> all_vals;
    for (int k = 0; k < n; ++k) {
        int idL = (2 * k) % n;
        int idR = (2 * k + 1) % n;
        for (int xu = 0; xu < 2; ++xu) {
            for (int xv = 0; xv < 2; ++xv) {
                int val = a[xu ? idL + n : idL] + a[xv ? idR + n : idR];
                all_vals.push_back(val);
            }
        }
    }
    sort(all_vals.begin(), all_vals.end());
    all_vals.erase(unique(all_vals.begin(), all_vals.end()), all_vals.end());
    int M = all_vals.size();
    vector<vector<tuple<int,int,int>>> entries(M);
    for (int k = 0; k < n; ++k) {
        int idL = (2 * k) % n;
        int idR = (2 * k + 1) % n;
        for (int xu = 0; xu < 2; ++xu) {
            for (int xv = 0; xv < 2; ++xv) {
                int val = a[xu ? idL + n : idL] + a[xv ? idR + n : idR];
                int idx = lower_bound(all_vals.begin(), all_vals.end(), val) - all_vals.begin();
                entries[idx].emplace_back(k, xu, xv);
            }
        }
    }

    // 建图：每个原始对 i (0..n-1) 是一个节点，边对应桌子
    vector<vector<tuple<int,int,bool>>> adj(n); // (desk, other_pair, need_transpose)
    for (int k = 0; k < n; ++k) {
        int idL = (2 * k) % n;
        int idR = (2 * k + 1) % n;
        adj[idL].emplace_back(k, idR, false);
        adj[idR].emplace_back(k, idL, true);
    }

    vector<bool> vis_pair(n, false);
    vector<int> desk_to_ring(n, -1), desk_pos(n, -1);
    vector<bool> desk_trans(n, false);
    vector<SegTree> rings;
    vector<bool> ring_ok;
    int bad_cnt = 0;

    // 找出所有环（每个环对应一个圆上的桌子序列）
    for (int i = 0; i < n; ++i) {
        if (vis_pair[i]) continue;
        vector<int> desks;
        vector<bool> trans;
        int cur = i;
        int prev_desk = -1;
        do {
            vis_pair[cur] = true;
            bool found = false;
            for (auto &e : adj[cur]) {
                int desk = get<0>(e);
                int nxt = get<1>(e);
                bool need = get<2>(e);
                if (desk != prev_desk) {
                    desks.push_back(desk);
                    trans.push_back(need);
                    prev_desk = desk;
                    cur = nxt;
                    found = true;
                    break;
                }
            }
            // 每个节点度数为2，且另一条边一定不是来路，故总能找到
            assert(found);
        } while (cur != i);
        int len = desks.size();
        int rid = rings.size();
        rings.emplace_back(len);
        ring_ok.push_back(false);
        bad_cnt++;
        for (int p = 0; p < len; ++p) {
            int k = desks[p];
            desk_to_ring[k] = rid;
            desk_pos[k] = p;
            desk_trans[k] = trans[p];
        }
    }

    vector<Mat> cur_mat(n);
    int l = 0, r = -1;
    int ans = INF;
    while (l < M) {
        // 扩大右边界直到所有环都可行
        while (r + 1 < M && bad_cnt > 0) {
            ++r;
            for (auto &tup : entries[r]) {
                int k = get<0>(tup), xu = get<1>(tup), xv = get<2>(tup);
                if (cur_mat[k].a[xu][xv] == 1) continue;
                cur_mat[k].a[xu][xv] = 1;
                int rid = desk_to_ring[k];
                int pos = desk_pos[k];
                bool need_trans = desk_trans[k];
                Mat leaf = need_trans ? transpose(cur_mat[k]) : cur_mat[k];
                rings[rid].upd(pos, leaf);
                Mat prod = rings[rid].query();
                bool new_ok = prod.trace();
                if (new_ok && !ring_ok[rid]) {
                    ring_ok[rid] = true;
                    bad_cnt--;
                } else if (!new_ok && ring_ok[rid]) {
                    ring_ok[rid] = false;
                    bad_cnt++;
                }
            }
        }
        if (bad_cnt == 0) {
            ans = min(ans, all_vals[r] - all_vals[l]);
        }
        // 移动左边界，撤销对应的矩阵元素
        for (auto &tup : entries[l]) {
            int k = get<0>(tup), xu = get<1>(tup), xv = get<2>(tup);
            if (cur_mat[k].a[xu][xv] == 0) continue;
            cur_mat[k].a[xu][xv] = 0;
            int rid = desk_to_ring[k];
            int pos = desk_pos[k];
            bool need_trans = desk_trans[k];
            Mat leaf = need_trans ? transpose(cur_mat[k]) : cur_mat[k];
            rings[rid].upd(pos, leaf);
            Mat prod = rings[rid].query();
            bool new_ok = prod.trace();
            if (new_ok && !ring_ok[rid]) {
                ring_ok[rid] = true;
                bad_cnt--;
            } else if (!new_ok && ring_ok[rid]) {
                ring_ok[rid] = false;
                bad_cnt++;
            }
        }
        ++l;
        if (r < l - 1) r = l - 1; // 左指针超过右指针时重置
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}