QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: Milmon

Posted at: 2026-01-20 20:14:08

Last updated: 2026-01-20 20:15:23

Back to Problem

题解

通过数学推导易知,令向量 $A_i = (2s_i - h_i - p_i, h_i - p_i)$,则 $i$ 赢 $j$ 当且仅当 $A_i$ 和 $A_j$ 的叉积 $> 0$。

计数只需要用总方案数减去不合法的情况,计数不合法的情况可以枚举第一个向量 $A_i$,使得 $A_i$ 和 $A_j, A_k$ 的叉积都 $> 0$,方案数即为叉积 $> 0$ 的 $j$ 中任意选择两个的方案数,这个方案数可以通过双指针求出。需要注意特殊处理重复的向量和相反的向量。

时间复杂度为 $\mathcal{O}(n \log n)$。

Comments

No comments yet.