题目
分析
本题用模拟法可以通过部分测试用例，但在数据量接近上限（\(10^5\))时，由于冒泡排序的基本特性：其时间复杂度是\(O(N^2)\)，所以会超时。
两个洞见
先根据一个示例来发现本题的关键。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|
| 原始数据位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 原始数据数值 | 50 | 20 | 80 | 60 | 10 | 40 | 70 |
| 稳定排序数值 | 10 | 20 | 40 | 50 | 60 | 70 | 80 |
| 稳定排序后元素原来的位置 | 5 | 2 | 6 | 1 | 4 | 7 | 3 |
从题目中给出的所谓双向冒泡法（“鸡尾酒”排序），一个数字最终到达正确的位置（比如40从6号位来到3号位，或者50从1号位来到4号位）需要通过“交换”位置来完成。
洞见一：有这样的交换，就说明没有排好序，因此程序会“moo”一次。因此“交换”次数等于“moo”的次数。
交换的方向有两个：左到右或者右到左。我们接下来要证明：这两个次数一定相等。
对于一个特定的位置（p），有两种操作：
L_p = { 原下标 > p 且 最终下标 ≤ p }，这些元素必须从右穿到左，跨越边界p。R_p = { 原下标 ≤ p 且 最终下标 > p }，这些元素必须从左穿到右，跨越边界p。
但是，对这个位置p而言，\([1, p]\)中有且仅有p个元素。如果原始区间中有k个元素应该在这个区间里，那么就有p-k个元素需要右穿左，也意味着有p-k个元素需要左穿右！所以两者相等。
洞见二：在这样的排序方法中，只要计算一个方向。
区间的关闭
当元素需要从位置j移动到位置i（\(i \lt j\)）时，形成一个穿越区间[i, j)，表示从右到左的穿越。它表明：
- 有一个元素原本在位置
right，现在要移动到位置left - 由于\(left \lt right\)，这个元素需要"从右到左穿越"
- 在扫描线算法中，当我们扫描到位置
left时，这个穿越开始（cnt++） - 当我们扫描到位置
right时，这个穿越结束（cnt--）
而vis[a[i].second]=1的作用是，表明这个位置是某个元素的原始出发点，将其标记为1是说这个元素已经出发了，不用再次出发，也就是配合了：
if(vis[i]==1) cnt--;至于为何先关闭区间后标记，是因为如果某个元素原位置就是i（即\(a[i].second == i\)），先执行vis[i]检查，再设置vis[i] = 1，避免同一轮循环的冲突。vis[i]有可能由之前别的元素标记，所以需要先检查是否有标记再进行标记。
每次循环不断保留最大的交换次数，就能得到最后答案。
// 扫描最终位置 i，统计需要跨越边界的“开放区间”数目
for (int i = 1; i <= N; ++i)
{
// 若该元素的原下标在当前位置 i 的右侧，开启一个穿越区间 [i, a[i].second)
// 该元素需要从右到左穿越，才能到达当前位置 i，计数+1
if (i < a[i].second)
cnt++;
// 若此前标记过有区间以边界 i 为右端点（原下标==i），在此关闭该区间
if (vis[i])
cnt--;
// 标记当前元素的原下标作为一个区间的右端点，供未来走到该下标时关闭（先关后标记，避免同位次干扰）
vis[a[i].second] = 1;
ans = max(ans, cnt);
}答案
思考
这道题很难！