题目理解

在一个环上有 $2N$ 个点，$N$ 个黑点，$N$ 个白点。需要画 $N$ 条线段连接黑白点，每个点恰好用一次。两条线段相交是指它们在环上交叉。目标是最大化相交的线段对数。

---

核心思路

1. 相交的几何条件

在环上，两条线段相交的充分必要条件是：它们的四个端点在环上交替出现。例如，按顺时针方向点的顺序为 $a, c, b, d$，且 $a$ 连接 $b$，$c$ 连接 $d$，则这两条线段相交。

2. 总对数分析

共有 $N$ 条线段，总共有 $\frac{N(N-1)}{2}$ 对线段。我们的目标是让尽量多的线段对相交。

3. 层状结构分解

将环上的匹配可以分解为多个层次：

• 同一层内的线段互不相交
• 不同层之间的线段一定相交

设匹配分为 $k$ 层，每层包含 $m_1, m_2, \dots, m_k$ 条线段，则：

• 同一层内的 $\frac{m_i(m_i-1)}{2}$ 对线段不相交
• 总不相交对数为 $\sum_{i=1}^k \frac{m_i(m_i-1)}{2}$
• 总相交对数 = $\frac{N(N-1)}{2} - \sum_{i=1}^k \frac{m_i(m_i-1)}{2}$

4. 最大化相交数的策略

要最大化相交数，需要最小化 $\sum_{i=1}^k \frac{m_i(m_i-1)}{2}$。

根据凸性，当层的大小尽可能均匀时，这个和最小。特别地，当每层只有 1 条线段时，不相交对数为 0，相交数达到理论最大值 $\frac{N(N-1)}{2}$。

5. 环上的实际限制

在环上，由于颜色排列的限制，我们无法总是达到每层 1 条线段。实际的最大相交数为：

$$\text{最大相交数} = \frac{N(N-1)}{2} - \frac{m(m-1)}{2} $$

其中 $m$ 是在最优匹配方案中，最大层的大小。

---

求解方法

括号匹配模型

将问题转化为括号匹配：

• 选择一种颜色作为左括号，另一种颜色作为右括号
• 在环上寻找匹配数最小的起点
• 该匹配数对应最大层的大小 $m$

具体步骤

1. 尝试两种颜色分配方案：

   • 方案一：黑点为左括号，白点为右括号
   • 方案二：白点为左括号，黑点为右括号

2. 对每种方案：

   • 计算环上所有起点的前缀和
   • 选择前缀和最小的位置作为起点（保证括号匹配有效）
   • 从该起点进行贪心匹配，统计匹配成功的数量

3. 取两种方案中的最小匹配数作为 $m$

4. 计算最终结果：

   $$\text{最大相交数} = \frac{N(N-1)}{2} - \frac{m(m-1)}{2} $$

---

正确性说明

该方法的核心在于：

• 环上的匹配可以分解为不相交的层
• 每层的匹配数对应括号匹配中同一嵌套深度的线段数量
• 最小化最大层的大小可以最大化交叉线段的数量
• 通过选择合适起点和颜色方向，可以找到最优的层状分解

---

复杂度分析

该方法的时间复杂度为线性：

• 只需要扫描环两次（两种颜色分配方案）
• 每次扫描包括计算前缀和和执行贪心匹配
• 总体时间复杂度为 $O(N)$