题解：三角剖分扇形转换问题

这道题要求我们处理正多边形三角剖分的操作与查询，核心是计算将当前三角剖分转换为以指定顶点为中心的扇形剖分所需的最小操作数和方案数。

一、问题分析

1. 基本概念

• 三角剖分：n 边形的三角剖分包含 n-3 条不相交的对角线，将多边形分成 n-2 个三角形。
• 扇形剖分：以顶点 x 为中心的扇形剖分是一种特殊的三角剖分，所有对角线都以 x 为一个端点。
• 操作：每次操作是移除一条对角线并添加一条新对角线，保持三角剖分的合法性。

2. 关键观察

• 最小操作数：要将当前剖分转换为以 x 为中心的扇形剖分，需要替换所有不以 x 为端点的对角线。因此最小操作数 = 总对角线数 - 以 x 为端点的对角线数。
• 方案数：每条非扇形对角线的替换方式是确定的，但替换顺序可以不同，方案数是这些可能顺序的乘积。

二、算法设计

1. 数据结构选择

• 树状数组（Fenwick Tree）：用于高效维护和查询方案数的乘积因子。
• 计数数组：记录每个顶点作为端点的对角线数量。

2. 核心算法

（1）预处理

• 计算阶乘数组 fac，用于后续方案数计算。
• 初始化树状数组，用于维护乘积因子。

（2）对角线更新操作

对于每条对角线 (x, y)：

• 维护计数数组 cnt，记录每个顶点作为端点的对角线数量。
• 通过树状数组的区间更新，维护不同顶点对应的方案数乘积因子：
  • 对于添加操作，乘以相应因子的逆元
  • 对于移除操作，乘以相应因子

（3）查询处理

• 最小操作数 = n-3 - cnt[x]
• 方案数 = 树状数组查询结果 × 阶乘值（模 10^9+7）

三、代码解析

1. 辅助函数

• readn：快速读取整数，优化输入效率
• ksm：快速幂实现，用于计算模逆元
• prep：预处理阶乘数组

2. 树状数组（T 结构体）

• 支持区间更新和单点查询，用于维护方案数的乘积因子
• addlr 函数通过差分思想实现区间更新

3. 对角线更新（upd 函数）

• 处理对角线的添加和移除
• 计算并更新两个关键因子：
  • c1：与对角线 (x,y) 相关的一个区域因子
  • c2：与对角线 (x,y) 相关的另一个区域因子
• 通过树状数组更新这些因子对不同顶点的影响

4. 主函数

• 初始化数据结构
• 处理初始对角线
• 循环处理每个事件：
  • 类型 1（操作）：更新对角线
  • 类型 2（查询）：计算并输出最小操作数和方案数

四、复杂度分析

• 预处理：O(N)
• 每个更新操作：O(log N)
• 每个查询操作：O(log N)
• 总复杂度：O(N + Q log N)，可处理 n, q ≤ 2×10^5 的数据规模

五、关键思路总结

1. 最小操作数计算基于简单计数，即需要替换的非扇形对角线数量
2. 方案数计算利用了乘法原理，通过树状数组高效维护不同区域的乘积因子
3. 模运算和逆元的使用确保了在大数情况下计算的正确性

该解法巧妙地将几何问题转化为代数计数问题，通过高效的数据结构实现了快速的更新和查询操作。