题目理解

在六边形无限平铺的平面上，Pak Dengklek 从初始格子出发，执行由 $N$ 次行动构成的行动序列，形成一条封闭、简单且暴露的路径。该路径及其内部格子构成一个领域。每个格子 $c$ 的距离 $d$ 定义为从初始格子出发，在领域内只经过领域中的格子到达 $c$ 所需的最少移动步数。每个格子的分数为 $A + d \cdot B$，其中 $A$ 和 $B$ 是给定的常数。要求计算领域中所有格子的分数之和，并对 $10^9+7$ 取模。

---

关键观察

1. 六边形网格的坐标表示

六边形网格可以使用立方体坐标或轴向坐标表示。本题中，通过定义六个移动方向 $(dx, dy)$，将网格映射到二维平面上，便于处理。

2. 路径的性质

• 封闭性：起点与终点相同。
• 简单性：除初始格子访问两次外，其他格子至多访问一次。
• 暴露性：路径上的每个格子都至少有一个相邻格子不在路径上且不是内部格子。

这些性质保证了路径围成的领域是一个单连通区域，没有“洞”，且边界是简单的闭合曲线。

3. 距离计算的规律

在领域内，格子的距离 $d$ 满足：

• 从初始格子出发，距离递增。
• 在领域的同一“层”中，距离相同的格子构成一个环状区域。
• 由于六边形网格的对称性，距离变化在网格中具有线性性质。

---

算法设计

1. 坐标旋转与线段提取

六边形网格有六个对称方向，通过旋转 $60^\circ$ 三次，每次只处理两个方向的边（旋转后对应 $x$ 坐标变化的边）。对于每次旋转：

• 将路径的每条边表示为一条线段，形式为 $y = kx + b$（$k$ 为 $0$ 或 $1$），并记录 $x$ 的取值范围 $[u, v]$。
• 所有线段构成路径在旋转后坐标系下的投影。

2. 扫描线构建区域树

• 收集所有线段的端点 $x$ 坐标，排序并去重。
• 从左到右扫描每个 $x$ 坐标，维护当前 $x$ 处所有线段的上下顺序（使用平衡树）。
• 根据线段的出现、消失和相交事件，将领域划分为若干个带状区域。每个区域由两个 $x$ 坐标 $[l_x, r_x]$ 和两条边界线段（上边界 $ly$、下边界 $ry$）定义。
• 这些区域之间的相邻关系构成一棵树（因为领域单连通），称为区域树。

3. 距离计算与分数求和

• 从包含初始格子的区域开始，进行深度优先搜索（DFS）。每个区域到初始格子的距离 $va$ 可通过父区域的距离加上 $x$ 坐标差值的绝对值得到。
• 对于每个区域，其内部格子的距离 $d$ 随 $x$ 线性变化。因此，该区域内所有格子的分数之和可以通过等差数列求和公式快速计算。
• 在计算过程中，需扣除相邻区域边界上的重复计数。

4. 合并三次旋转的结果

• 每次旋转处理了两个方向的边，将三次旋转计算出的分数贡献相加，即得到最终答案。

---

算法正确性

1. 旋转覆盖的完备性

六边形网格有六个方向，每旋转 $60^\circ$ 后，原本六个方向变为另外六个方向。通过三次旋转（每次旋转 $60^\circ$），可覆盖所有方向的边，确保所有格子都被计入。

2. 区域划分的合理性

扫描线算法将领域划分为一系列不重叠的带状区域。由于路径是简单闭合曲线，这些区域恰好覆盖整个领域，且区域间的邻接关系形成一棵树（无环）。

3. 距离计算的正确性

在六边形网格中，从一个区域到相邻区域，距离的变化与 $x$ 坐标的移动步数一致。因此，通过 DFS 逐区域递推距离是正确的。

4. 分数求和的准确性

每个区域内格子的距离是 $x$ 的线性函数，分数 $A + d \cdot B$ 也是线性函数。对线性函数在整数区间上求和，可通过数学公式直接计算，避免逐格枚举。

---

复杂度分析

时间复杂度

• 线段提取：$O(N)$。
• 扫描线构建区域树：$O(N \log N)$，因为每个线段事件需要在平衡树中插入、删除或查询，每次操作 $O(\log N)$。
• DFS 计算贡献：$O(N)$，每个区域的计算是 $O(1)$。
• 总时间复杂度为 $O(N \log N)$，对于 $N \leq 200\,000$ 可接受。

空间复杂度

• 存储线段、事件、区域树等数据结构需要 $O(N)$ 空间。

---

代码实现要点

1. 数据结构定义

struct line {
    int u, v; // x 范围
    int k, b; // y = k*x + b
};

struct node {
    int lx, rx; // x 范围
    int ly, ry; // 上下边界线段的索引
};

struct Edge {
    int to, t; // 相邻区域，以及相邻的 x 坐标
};

2. 扫描线事件处理

• 每个 $x$ 坐标处，收集所有以该 $x$ 为端点的线段。
• 按照线段在当前 $x$ 处的 $y$ 值排序，用平衡树维护顺序。
• 处理线段的开始、结束和相交事件，更新区域树。

3. 分数计算

// 对于区域 u，计算其贡献
贡献 = (基础分数 + 距离系数 * 距离) * 格子数量
      + 距离系数 * (等差数列求和)

4. 旋转与合并

long long ans = 0;
for (int rot = 0; rot < 3; rot++) {
    // 旋转方向
    for (int i = 0; i < N; i++) D[i] = (D[i] + 1) % 6;
    ans += solve_one_rotation();
    ans %= MOD;
}

---

算法标签

• 平面图
• 坐标变换
• 树形结构
• 平衡树
• 分治

---

总结

本题通过坐标旋转将六边形网格问题转化为三个二维坐标系下的线段问题，利用扫描线技术构建区域树，再通过树形DFS和等差数列求和高效计算分数总和。算法避免了直接枚举大量格子，将时间复杂度优化至 $O(N \log N)$，能够处理 $N$ 高达 $200\,000$、总步数达 $10^9$ 的大规模数据。