题目大意

我们有一个 $n$ 个顶点的凸多边形，初始时已经通过 $n-3$ 条不相交的对角线（加上 $n$ 条边）将多边形三角剖分。
定义一种 旋转操作：
若存在四个顶点 $a < b < c < d$，且它们之间恰有 $5$ 条边（即 $(a,b),(b,c),(c,d),(a,d),(a,c)$），则可以把 $(a,c)$ 删去，添加 $(b,d)$。

游戏过程：从某个初始三角剖分状态出发，不断进行旋转操作，直到无法旋转为止。
要求：

• 对于 $S_0$（初始三角剖分）和 $m$ 个由 $S_0$ 旋转一次得到的新状态 $S_i$，分别求出从它们开始到无法旋转的 最少步数，以及当 $W=1$ 时求出最少步数的 方案数（对 $10^9+7$ 取模）。

问题转化与核心思路

这个问题本质上是 三角剖分的翻转距离 问题：

1. 三角剖分与二叉树
   任意一个 $n$ 边形的三角剖分可以对应一棵有 $n-2$ 个叶子的二叉树（通过把三角形作为节点，相邻三角形连边）。
   旋转操作对应于二叉树的 旋转（改变局部结构）。

2. 目标状态
   无法旋转的状态对应一个特殊的三角剖分——所有对角线都从一个顶点出发（扇状剖分）。
   在二叉树表示中，这对应一个 链（完全偏斜的二叉树）。

3. 最少旋转次数
   从任意三角剖分到目标剖分的最少旋转次数 = 当前三角剖分中“需要被移除”的对角线数量。
   更具体地，如果固定目标剖分为从顶点 $1$ 出发的所有对角线 $(1,3),(1,4),\dots,(1,n-1)$，那么初始剖分中不在这个集合的对角线都需要通过旋转移除。

4. 方案数
   最少步数的方案数是一个组合计数问题：每一步可以移除某条“可旋转”的对角线，但顺序会影响后续可用的旋转，方案数等于这些操作的某种拓扑排序数量。

代码解析

数据结构

• l[i]：顶点 $i$ 在三角剖分中向左（编号较小）的最远相邻顶点（除了 $i-1$ 这条边）。
• r[i]：顶点 $i$ 在三角剖分中向右（编号较大）的最远相邻顶点（除了 $i+1$ 这条边）。
• p[i]：顶点 $i$ 在三角剖分中除了 $l[i]$ 外另一个编号较小的相邻顶点（用于记录旋转的另一个端点）。
• ans：最少旋转次数。
• cnt：最少旋转次数的方案数（对 $mod$ 取模）。

初始化

• 读入 $W$ 和 $n$。
• 预处理逆元 $inv[]$（用于组合数计算）。
• 初始化 $l[i] = i-1, r[i] = i+1, p[i] = i$（初始为链状剖分）。

读入初始三角剖分

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

• 更新 r[x] = max(r[x], y)。
• 更新 l[y] 和 p[y]。
• 调用 update(x, y, 1) 增加计数。

update 函数

• 当添加一条对角线 $(l, r)$ 时：
  • ans++（需要多一次旋转来移除它）。
  • 更新方案数 cnt：乘以逆元和当前 ans，具体组合意义与移除顺序有关。
• 当移除一条对角线时反向操作。

处理查询

对于每个 $S_i$（由 $S_0$ 旋转 $(a,c)$ 得到）：

1. 找到旋转涉及的四个顶点 $a,b,c,d$（$b = p[c], d = r[c]$）。
2. 先移除 $(a,c)$，再添加 $(b,d)$，计算新状态的最少步数和方案数。
3. 输出后恢复原状态（因为下一个查询还是基于 $S_0$）。

关键结论

1. 最少旋转次数 = 初始三角剖分中不满足“从顶点 1 出发”的对角线数量。
2. 方案数 的计算基于这些对角线可以按任意顺序移除，但受依赖关系限制，公式为： $ \text{方案数} = \frac{(\text{总步数})!}{\prod (\text{各区间长度}-1)} $ 其中区间长度指对角线 $(l,r)$ 的 $r-l-1$。