题目理解

有 $N$ 个怪兽，每个怪兽的力量值是 $0$ 到 $N-1$ 的一个排列。我们可以让任意两个怪兽打架，根据力量值的差值决定胜负：

• 如果 $|S_a - S_b| = 1$，则力量值较小的怪兽获胜
• 如果 $|S_a - S_b| > 1$，则力量值较大的怪兽获胜

我们需要通过至多 $25\,000$ 次打架，确定每个怪兽的力量值。

---

关键观察

1. 胜负规则的本质

• 当两个怪兽力量值相邻时，胜负结果会"反转"：力量值小的获胜
• 当两个怪兽力量值不相邻时，胜负结果"正常"：力量值大的获胜
• 这提供了判断两个怪兽是否相邻的方法

2. 排列性质

• 所有力量值构成 $0$ 到 $N-1$ 的排列，没有重复
• 力量值 $0$ 的怪兽只能赢力量值 $1$ 的怪兽，对其他所有怪兽都会输
• 力量值 $N-1$ 的怪兽只能输给力量值 $N-2$ 的怪兽，对其他所有怪兽都会赢

3. 比较函数的设计

由于直接比较力量值大小不可行，我们可以定义一个比较函数：

• cmp(a, b) = Query(a, b)，即 $a$ 赢 $b$ 返回真
• 但这个函数不满足传递性，不能直接用于排序

---

算法设计

1. 分治构建初始序列

归并排序框架

使用归并排序对怪兽进行排序，但使用自定义的 cmp 函数：

void Sort(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    Sort(l, mid);
    Sort(mid + 1, r);
    // 合并两个有序子序列
}

虽然 cmp 不满足传递性，但通过这种分治方式得到的序列具有一定的局部有序性。

2. 寻找关键怪兽（最小值候选）

筛选策略

1. 从排序结果中取前 $\min(N, 10)$ 个怪兽作为候选
2. 在候选集中剔除那些输给多个其他候选的怪兽
3. 进一步检查候选怪兽是否会被前 $10$ 个不在候选集中的怪兽打败

确定关键点

• 最终保留的候选怪兽中，选择一个作为"疑似最小值"
• 如果候选有多个，选择在它们之间比较中获胜的那个（因为相邻时小者胜）

3. 序列重构与调整

定位关键位置

在初始序列中找到疑似最小值的怪兽位置 $r$

分段反转调整

int l = 0;
while (l < n) {
    int p = r + 1;
    // 找到下一个使得 cmp(a[l], a[p]) 为假的 p
    while (p < n && cmp(a[l], a[p])) p++;
    // 反转 [l, r] 区间
    reverse(a.begin() + l, a.begin() + r + 1);
    l = ++r;
    r = p;
}

这个调整过程基于以下原理：

• 如果 cmp(a[l], a[p]) 为真，说明这两个怪兽可能不相邻
• 通过反转操作，逐步将序列调整到正确的力量值顺序

4. 生成最终答案

调整后的序列 a 中，怪兽按力量值从小到大排列，因此：

• 位置 $i$ 的怪兽力量值就是 $i$
• 建立映射 b[a[i]] = i 得到每个怪兽的力量值

---

算法正确性

1. 关键怪兽的正确性

• 力量值 $0$ 的怪兽在候选筛选中具有特殊性质：它只会赢一个怪兽（力量值 $1$）
• 通过多层筛选，可以高概率找到真正的最小值

2. 调整过程的正确性

• 调整算法利用了相邻怪兽和不相邻怪兽的胜负规律
• 分段反转操作实际上是在修复序列中的"逆序对"
• 最终得到的序列满足：对于任意 $i<j$，如果 $j-i=1$ 则 cmp(a[i], a[j]) 为真，否则为假

3. 整体正确性保证

• 算法基于力量值排列的唯一性
• 通过有限的比较和调整，可以唯一确定力量值顺序
• 对于适应性的评测器，算法仍然有效

---

复杂度分析

时间复杂度

• 归并排序：$O(N \log N)$ 次比较
• 候选筛选：$O(\min(N, 10)^2) = O(100)$ 次比较
• 序列调整：$O(N)$ 次比较
• 总比较次数：约 $N \log N + O(N)$
• 对于 $N \leq 1000$，最坏约 $1000 \times 10 + 1000 = 11000$ 次比较

空间复杂度

• 存储比较结果的映射：$O(N^2)$ 最坏，但实际使用较少
• 其他数组：$O(N)$
• 总空间：$O(N^2)$，对于 $N=1000$ 可接受

询问次数分析

• 理论最坏：约 $11000$ 次 Query 调用
• 实际运行：通常远少于 $10000$ 次
• 远低于限制的 $25000$ 次

---

代码实现要点

1. 数据结构设计

vector<int> a;          // 怪兽序列
vector<int> b;          // 结果数组
map<pair<int, int>, bool> mp;  // 记忆化比较结果

2. 关键函数实现

• cmp()：带记忆化的比较函数，避免重复询问
• Sort()：归并排序实现
• 候选筛选：多层过滤确保找到最小值
• 序列调整：分段反转重构序列

3. 优化技巧

• 记忆化比较结果，避免重复 Query
• 只对前 $10$ 个怪兽进行详细筛选，减少不必要的比较
• 调整过程中，利用已知信息减少比较次数

4. 边界处理

• $N$ 较小的情况（如 $N=4$）
• 候选集大小不足的情况
• 调整过程中边界条件的处理

---

算法标签

• 分治算法
• 归并排序
• 构造

---

总结

本题通过巧妙的比较函数设计和序列调整策略，在有限的询问次数内解决了怪兽力量值的推断问题。算法的核心在于：

1. 利用分治排序获取初始有序性
2. 通过筛选找到关键怪兽（最小值）
3. 基于胜负规则调整序列至完全有序

该算法在 $N \leq 1000$ 时询问次数远低于限制，且对适应性评测器鲁棒，体现了分治思想和问题转化的应用价值