题目大意

给定一个长度为 $N$ 的整数序列 $A$。
我们可以选择交换任意两个位置（不需要相邻）的元素，得到新序列 $A'$。
然后用标准的冒泡排序（从左到右扫描，相邻逆序就交换）对 $A'$ 进行排序，要求 冒泡排序中的交换次数 尽可能小。
输出这个最小交换次数。

---

关键性质

1. 冒泡排序的交换次数

对于一个序列，冒泡排序中交换的次数 = 序列的 逆序对总数。
这是因为每次交换恰好减少一个逆序对，而冒泡排序每次只交换相邻逆序对。

所以问题等价于：

交换任意两个位置一次后，得到的新序列 $A'$，希望它的逆序对数尽量小。

---

2. 交换两个元素对逆序对数的影响

设原序列为 $a[1 \dots n]$，交换位置 $x$ 和 $y$（$x < y$，值分别是 $a_x, a_y$）。
原来与 $a_x, a_y$ 相关的逆序对数会发生变化。

如果 $a_x = a_y$，交换后逆序对数不变。

否则，可以把区间分成三段：

1. 左段：$i < x$
2. 中段：$x < i < y$
3. 右段：$i > y$

推导可得：

• 若 $a_x < a_y$：交换后逆序对数变化量

  $$\Delta = - \text{(中段值在 }[a_x+1, a_y]\text{ 的个数)} - \text{(中段值在 }[a_x, a_y-1]\text{ 的个数)} - 1 $$

• 若 $a_x > a_y$：交换后逆序对数变化量

  $$\Delta = + \text{(中段值在 }[a_y+1, a_x]\text{ 的个数)} + \text{(中段值在 }[a_y, a_x-1]\text{ 的个数)} + 1 $$

这里的 “中段值在某个区间内的个数” 是值位于该区间内的位置数量。

我们可以用 权值线段树可持久化（主席树） 快速查询任意区间内值在某个权值范围的个数。

---

3. 选择交换的优化

暴力枚举所有 $x, y$ 是 $O(n^2)$ 的，不可行。
需要利用单调性优化。

设：

• $Pre$：从左到右的 前缀最大值位置（即满足 $a[i] > a[Pre[j-1]]$ 的第一个位置）
• $Suf$：从右到左的 后缀最小值位置（即满足 $a[i] < a[Suf[k-1]]$ 的第一个位置）

因为最优的交换通常是 前缀最大值位置 和 后缀最小值位置 进行交换，这样才能最大程度减少逆序对。

---

证明思路（简化）： 为了减少逆序对，我们希望把大的数往右移，小的数往左移。
前缀最大值位置是“阻碍”序列升序的大数位置（它比左边所有数都大，但却不是全局最大，说明它右边有比它小的数，形成逆序）。
后缀最小值位置是“阻碍”序列升序的小数位置（它比右边所有数都小，但却不是全局最小，说明它左边有比它大的数，形成逆序）。
交换这两个位置通常能得到较大的逆序对减少。

---

4. 利用四边形不等式（或决策单调性）优化枚举

如果我们固定 $x$ 在 $Pre$ 中选，$y$ 在 $Suf$ 中选，计算减少量 $f(x,y)$，发现它有 决策单调性（满足四边形不等式）。
于是可以用 分治优化 在 $O(m \log m)$ 内找到最优的 $x,y$，其中 $m = |Pre| + |Suf|$，通常 $m \ll n$。

---

代码步骤解析

Step 1：读入与离散化

FOR(i, 1, n) cin >> a[i], b[i] = a[i];
sort(b + 1, b + n + 1);
b[0] = unique(b + 1, b + n + 1) - b - 1;
FOR(i, 1, n) a[i] = lower_bound(b + 1, b + b[0] + 1, a[i]) - b;

将值离散化到 $1 \dots b[0]$，方便使用数据结构。

---

Step 2：建主席树

FOR(i, 1, n) seg.Plus(a[i], seg[i], seg[i-1]);

seg[i] 表示前 $i$ 个元素的权值线段树根，可以快速查询区间 $[l, r]$ 中值在某个范围内的个数。

---

Step 3：计算原序列逆序对总数 sum

用树状数组从右往左扫：

DOR(i, n, 1) sum += bit.Sum(a[i] - 1), bit.Plus(a[i]);

如果 sum == 0 表示原序列已有序，但题目要求必须交换一次，所以若所有值不同（b[0] == n）则交换一次会产生 1 个逆序对，否则可能找到相等值交换后逆序对仍为 0。

---

Step 4：建立 Pre 和 Suf 数组

a[Pre[pr = 0] = 0] = 0, a[Suf[su = 0] = n + 1] = b[0] + 1;
FOR(i, 1, n) if (a[i] > a[Pre[pr]]) Pre[++pr] = i;
DOR(i, n, 1) if (a[i] < a[Suf[su]]) Suf[++su] = i;
reverse(Suf + 1, Suf + su + 1);

Pre 存从左到右的前缀最大值位置，Suf 存从右到左的后缀最小值位置（反转后是递增下标）。
并在两端加入哨兵（0 和 $b[0]+1$）方便处理。

---

Step 5：函数 Sum(l, r)

计算交换位置 l 和 r 后逆序对减少量：

• 若值相等，减少 0。
• 若 $a[l] < a[r]$（交换后大数左移，小数右移，逆序对减少），公式对应上面推导。
• 若 $a[l] > a[r]$（交换后小数左移，大数右移，逆序对增加），公式对应推导。

用主席树查询区间 $(l, r)$ 中值在某个范围内的个数。

---

Step 6：决策单调性分治优化 Sep

void Sep(int l, int r, int L, int R) {
    if (l > r || L > R) return;
    int mid = (l+r)>>1, Mid = 0;
    FOR(i, L, R) {
        int val = Sum(Pre[mid], Suf[i]);
        if (val > f[mid]) f[mid] = val, Mid = i;
    }
    Sep(l, mid-1, L, Mid);
    Sep(mid+1, r, Mid, R);
}

对 $Pre$ 的每个下标 $mid$，在 $Suf$ 的某个区间找最优的 $i$，满足决策单调性，分治找。

$f[mid]$ 记录 $Pre[mid]$ 与某个 $Suf$ 交换的最大减少量。

---

Step 7：输出结果

FOR(i, 1, pr) tomax(ans, f[i]);
cout << sum - ans << endl;

原逆序对 $sum$ 减去最大减少量 $ans$，就是最小交换次数。

---

时间复杂度

• 离散化 $O(n \log n)$
• 建主席树 $O(n \log n)$
• 计算原逆序对 $O(n \log n)$
• 分治优化 $O(m \log m)$，$m \approx O(\sqrt{n})$ 或更小
• 每次查询 Sum $O(\log n)$

总复杂度 $O(n \log n)$，可过 $10^5$。

---

总结

这道题综合了：

1. 逆序对与冒泡排序交换次数的关系
2. 离散化与树状数组
3. 主席树（可持久化线段树）查询区间权值个数
4. 利用前缀最大值与后缀最小值优化候选位置
5. 决策单调性分治优化枚举

最终目标是最小化交换一次后的逆序对数，输出该逆序对数作为冒泡排序交换次数。