题意理解

• 有 $n$ 个球员，编号 $1$ 到 $n$。
• 有三种场地（类型 1、2、3），每种场地有一个球员排名列表（从最强到最弱）。
• 每两名球员之间恰好比赛一场，共 $\frac{n(n-1)}{2}$ 场。
• 每场比赛选择一个场地，规则如下：
  1. 第一准则：选择让胜者排名最靠前（名次数值最小）的场地。
  2. 第二准则：如果多个场地胜者排名相同，则选择让败者排名最靠前的场地。
  3. 第三准则：如果仍相同，选择编号最小的场地。
• 输出：
  • 第一行：三种场地各自举办的比赛数量。
  • 第二行：每个球员赢的场次数（注意：在选定的场地上，排名高的球员必胜）。

---

核心难点

直接枚举所有 $n(n-1)/2$ 场比赛对 $n \le 10^5$ 不可行（$O(n^2)$ 太大）。

必须找到方法批量确定多场比赛的场地和结果。

---

关键观察

1. 排名转换

设 $r_{k,i}$ 表示球员 $i$ 在场地 $k$ 上的排名（1 最强，$n$ 最弱）。

对于任意一对球员 $(a,b)$，在场地 $k$ 上：

• 胜者是 $a$ 当且仅当 $r_{k,a} < r_{k,b}$。
• 胜者的排名是 $\min(r_{k,a}, r_{k,b})$。
• 败者的排名是 $\max(r_{k,a}, r_{k,b})$。

2. 场地选择规则

对于 $(a,b)$，比较三元组：

$$\big(\min(r_{1,a}, r_{1,b}),\ \max(r_{1,a}, r_{1,b}),\ 1\big) $$$$\big(\min(r_{2,a}, r_{2,b}),\ \max(r_{2,a}, r_{2,b}),\ 2\big) $$$$\big(\min(r_{3,a}, r_{3,b}),\ \max(r_{3,a}, r_{3,b}),\ 3\big) $$

按字典序比较（先比较第一个元素，小者优；再比较第二个元素，小者优；最后比较第三个元素，小者优），最优的场地就是胜出的那个三元组对应的场地编号。

---

高效算法思路

步骤 1：预处理排名映射

建立数组 pos[k][i] 表示球员 $i$ 在场地 $k$ 的排名（1-based 或 0-based 均可）。

步骤 2：避免枚举所有对

我们考虑按获胜者在某个场地的排名来批量处理。

对于某个场地 $k$，如果我们固定一个排名 $p$（1 到 $n$），那么排名 $p$ 的球员在该场地能战胜所有排名 $>p$ 的球员。

但是，一场比赛是否真的在场地 $k$ 举行，还要和其他场地比较。

---

步骤 3：批量判定方法

一个有效的方法是：

1. 对每个场地 $k$，按该场地的排名顺序处理球员。

2. 维护一个集合 $S$，表示尚未被分配到更优场地的球员集合。

3. 从最强（排名 1）到最弱（排名 $n$）遍历：

   • 对于当前球员 $x$（排名 $p$），他与集合 $S$ 中所有排名低于他的球员（即还未处理的球员）的比赛，可能在场地 $k$ 举行。
   • 但必须检查：对于 $S$ 中的每个球员 $y$，场地 $k$ 是不是 $(x,y)$ 的最优场地。
   • 检查方法：比较三元组 $(p, r_{k,y}, k)$ 与其他场地的三元组。

4. 优化检查：

   • 如果 $S$ 很大，直接枚举 $S$ 中每个元素会超时。
   • 实际上，我们可以利用单调性：当 $p$ 固定时，随着 $r_{k,y}$ 增大，场地 $k$ 的相对优势可能变化。
   • 但更简单的方法：预先计算所有 $(x,y)$ 的最优场地是困难的。

---

步骤 4：已知可行解法（简述）

一种可行的高效解法（$O(n \log n)$ 或 $O(n \log^2 n)$）：

• 把问题看作：有 $n$ 个点，每对点之间有一个标签（场地编号），标签由上述三元组最小字典序决定。

• 对每个场地 $k$，我们想知道有多少对 $(a,b)$ 的标签是 $k$。

• 考虑对每个场地 $k$，用扫描线 + 数据结构统计：

  • 按该场地排名从小到大扫描球员 $a$。
  • 对每个 $a$，考虑它与排名比它低的球员 $b$ 的比赛。
  • 用数据结构（如 Fenwick 树/线段树）维护那些尚未被更优场地占用的球员 $b$，并且场地 $k$ 对 $(a,b)$ 是最优的。
  • 判断最优性：对于 $(a,b)$，若存在另一个场地 $t$ 使得 $(\min(r_{t,a},r_{t,b}), \max(...), t)$ 字典序更小，则排除。

• 具体实现时，可以先按第一关键字（胜者排名）分组，再按第二关键字（败者排名）处理。

---

步骤 5：球员胜场计算

一旦知道每场比赛的场地 $k$ 和胜者（即该场地上排名较高的球员），就可以累加每个球员的胜场数。

---

复杂度

• 暴力 $O(n^2)$ 适用于 $n \le 300$。
• 优化后可达 $O(n \log n)$ 或 $O(n \log^2 n)$，能处理 $n \le 10^5$。

---

总结

这道题的关键在于：

1. 将场地选择规则转化为三元组字典序比较。
2. 利用扫描线思想，按排名顺序处理，用数据结构批量统计符合条件的比赛。
3. 避免显式枚举所有球员对，而是通过维护候选集和快速排除非最优来减少计算量。