假设 $n=12$ ， $m=3$ 条弦分别为 $(2,4),(4,6),(9,10)$ ，那么这 $3$ 条弦实际上将链分成了 $6$ 个部分： $[1,2],[2,4],[4,6],[6,9],[9,10],[10,12]$ 。注意到这 $6$ 个部分中，只有弦对应的区间 $[2,4],[4,6],[9,10]$ 才有端点颜色不同的限制，其他区间是没有这一限制的，最后还要求两端的颜色不同。

不妨采用增量法统计，记录 $f_0,f_1$ 表示当前的部分中，末尾点与第一个点的颜色不同或相同的方案数。初始时显然也有 $f_0=0,f_1=1$ 。

现在加入一个新部分，假设这一部分中，首尾点颜色相同的方案数为 $g_1$ ，首尾点颜色不同的方案数为 $g_0$ （求 $g_0,g_1$ 就是 Part 1，显然对于弦对应的区间，需要强制钦定 $g_1=0$ ）。

那么有转移（两条转移依次进行）：

\begin{aligned} &f_1\gets f_0\cdot \frac{g_0}{k-1}+f_1\cdot g_1\\ &f_0\gets (f_0+f_1)\cdot (g_0+g_1)-f_1 \end{aligned}

第二条转移就是在计算补集方案，关键在于第一条转移。

假如这一部分的首端点与整条链的第一个端点相同，那么这一部分的首尾点颜色也就相同了，直接乘上方案即可 $f_1\cdot g_1$ ，否则我们需要强制钦定 $g_0$ 中最后一个点颜色为整条链的第一个端点相同，由于对于这一部分的最后一个点的颜色，每种颜色都是对称的，所以直接除以 $k-1$ 就可以了。

时间复杂度 $O(m\log (n+m))$ ，其中 $O(m\log m)$ 来自于对所有弦的排序。

Part 3

考虑一般的问题。由于区间两两或无交，或包含。那么根据处理该类问题的经验，很容易将所有区间建树。

这个树和常见的线段树或 BIT 相似。具体地，我们将每个区间看成一个节点，它在树上的深度为包含它的区间数量（这里将 $[1,n]$ 需要考虑的一个区间），若区间 $A$ 包含区间 $B$ ，则在树上， $A$ 为 $B$ 的祖先。

（由于我不是很会画图，所以就不画图了，大家可以拿笔出来自己试试）

这个树的建法很多，比如按照大小排序，查找这个区间被哪一个区间覆盖之类的（这一步注意细节）。

建出这个树后，我们可以沿用 Part 2 的过程，只需要将 Part 2 中对于一个部分直接调用 Part 1 改为如果这是一条弦对应的区间递归下去就可以了。

时间复杂度不变，仍然为 $O(m\log(n+m))$ 。

Submission in QOJ。