题目大意

给你一个长度为 $n$ 的排列 $p$。
对于每个位置 $i$，你可以选择：

• $a_i = p_i$
• 或 $a_i = 2n - p_i$

要求最小化最终数组 $a$ 中的逆序对数量。

核心观察

1. 值域与镜像

由于 $p_i$ 在 $[1, n]$ 之间，$2n - p_i$ 在 $[n, 2n-1]$ 之间。
因此每个位置的两个候选值：

• 小值 $p_i$
• 大值 $2n - p_i$

并且对于任意 $i, j$，如果有 $p_i < p_j$，那么：

• $p_i < p_j$
• $p_i < 2n - p_j$ （因为 $2n-p_j \ge n$）
• $2n - p_i > p_j$
• $2n - p_i > 2n - p_j$

关键性质：
两个数之间的大小关系是否发生变化，只取决于 数值较小的那个数 是否被镜像。
换句话说：

• 如果 $x < y$，则：
  • 保持 $x$，无论 $y$ 怎么选，$x < y$ 始终成立。
  • 将 $x$ 镜像为 $2n-x$，则无论 $y$ 怎么选，$2n-x > y$ 始终成立。
  • 改变 $y$ 不会影响 $x$ 与 $y$ 的比较结果。

2. 逆序对的来源

考虑当前处理的值 $v = p_i$ 和它的镜像 $2n-v$。

• 如果保持为小值 $v$：
  所有在 $i$ 左边且值大于 $v$ 的元素，一定会与 $i$ 构成逆序（因为 $v$ 小）。
• 如果镜像为大值 $2n-v$：
  所有在 $i$ 右边且值大于 $v$ 的元素，一定会与 $i$ 构成逆序（因为 $2n-v$ 很大，右边那些值无论如何镜像都小于它）。

并且，这些逆序不会与后面处理的值重复计算，因为当我们按数值从小到大处理时，当前值是当前最小的未确定元素。

算法步骤

1. 记录每个值在排列中的位置：pos[val] = index。
2. 初始化一个树状数组（Fenwick Tree），所有位置标记为 $1$（表示未处理）。
3. 按数值 $val = 1, 2, \dots, n$ 从小到大处理：
   • 找到该值的位置 $idx = pos[val]$。
   • 查询左边剩余元素个数 $left$ = query(idx-1)。
   • 查询右边剩余元素个数 $right$ = total - query(idx)。
   • 当前值对逆序数的贡献为 $\min(left, right)$，累加到答案。
   • 从树状数组中删除位置 $idx$（表示该值已处理，以后不再参与比较）。
4. 输出总逆序数。

为什么贪心正确

因为：

• 处理当前最小值 $v$ 时，所有比它大的值还未确定，但无论如何镜像，它们都比 $v$ 大（如果 $v$ 保持小）或比 $2n-v$ 小（如果 $v$ 镜像）。
• 处理完 $v$ 后，它不会再与任何后续值产生新的比较关系，因为：
  • 如果保持小值，它已是全局最小。
  • 如果镜像为大值，它已是全局最大（因为后续值镜像后只会变小）。
• 因此每次选择 $\min(left, right)$ 就是局部最优，且不影响后续选择，所以全局最优。

时间复杂度

• 树状数组操作 $O(\log n)$
• 每个值处理一次：$O(n \log n)$
• 总复杂度 $O(n \log n)$，满足 $n \le 5000$ 的限制。

示例解析

以输入：

3
2 1 3

• 值 $1$ 在位置 $2$：左边剩余 $1$ 个元素，右边剩余 $2$ 个元素 → 贡献 $\min(1,2)=1$。
• 删除位置 $2$，值 $2$ 在位置 $1$：左边剩余 $0$，右边剩余 $2$ → 贡献 $0$。
• 值 $3$ 在位置 $3$：左边剩余 $1$，右边剩余 $0$ → 贡献 $0$。

总逆序 = $1$，与样例输出一致。

代码实现（核心部分）

vector<int> bit(n + 2, 0);
auto update = [&](int idx, int delta) {
    for (++idx; idx <= n + 1; idx += idx & -idx)
        bit[idx] += delta;
};
auto query = [&](int idx) {
    int res = 0;
    for (++idx; idx > 0; idx -= idx & -idx)
        res += bit[idx];
    return res;
};

for (int i = 0; i < n; ++i) update(i, 1);

long long ans = 0;
for (int val = 1; val <= n; ++val) {
    int idx = pos[val];
    int left = query(idx - 1);
    int right = query(n - 1) - query(idx);
    ans += min(left, right);
    update(idx, -1);
}
cout << ans << "\n";

总结

本题的关键在于发现：

• 比较结果只由较小值是否镜像决定。
• 按值从小到大处理，可以保证当前决策不影响后续结果，从而使用贪心。
• 用树状数组动态维护剩余元素，即可 $O(n \log n)$ 求解。