- 11.3
- 考虑要以 \(x\) 为端需要的操作次数为 \(n - 3\) - 以 \(x\) 为端的个数
- 考虑方案数
- 如果有 \((x,p),(x,q),(p,q)\) 那一定存在一个 \(r\) 有 \((p,r),(q,r)\) 则可以把 \((p,q)\) 变成 \((x,r)\)
- 将所有对角线写成不经过 \(x\) 的弧的形式
- 任意两个弧要么包含要么交的长度为 0
- 每次操作都是选择一个不被别的弧包含的弧（极大弧），并删去
- 考虑 \((p,q)\) 被删去后会产生 \((p,r),(r,q)\) 这两条可删去的弧
- 我们可以把这个东西看成一个树形结构
- 故我们可以把问题转换为求取森林的拓扑序数量
- 一棵 \(m\) 个点的森林的拓扑序的数量即为 \(\frac{m!}{\prod\limits_{i} siz_i}\) , 这里的 \(m\) 即为两端均不为 \(x\) 的对角线数量
- 考虑 \(l-r\) 的弧的子树大小为 \(r-l-1\)
- 故考虑修改操作是区间乘，即可用线段树维护
-
11.4
