D
考虑枚举最大边，分别计算从两个端点出发能走到多少个点。
可以发现并查集能够很好地拟合这个过程，于是将边从小到大加入，每次合并的两个点集即为所求。
E
考虑贪心。从小到大枚举每一个盒子 \(i\)，所有满足 \(L \leqslant i\) 的球都可以放进这个盒子（如果 \(R \lt i\) 则无解），容易发现要选择 \(R\) 最小的球放进当前盒子。
但是由于盒子数量很大，所以不能枚举盒子。考虑将所有区间按 \(L\) 从小到大排序，记 \(p\) 表示当前填到哪个盒子了，将所有满足 \(L \leqslant p\) 的盒子以 \(R\) 为关键字加入小根堆，此时维护 \(p\) 是简单的。
时间复杂度 \(\Theta(n \log n)\)。
F
首先考虑求解本质不同子序列数量。设 \(f_{i}\) 表示考虑到 \(s_{i}\) 且 \(s_{i}\) 必选的方案数。
可以发现不同子序列个数是好求的，转移方程为 \(f_{i} = \sum \limits_{j = 0}^{i - 1} f_{j}\)，但如何去除重复的子序列呢？
令 \(k\) 为满足 \(s_{k} = s_{i}, k \lt i\) 的最大整数，注意到在这种转移方式下会得出相同的子序列当且仅当在 \(f_{j} (j \lt k)\) 的后面直接接上了 \(s_{i}\)，于是本质不同子序列计数的转移方程为 \(f_{i} = \sum \limits_{j = 0}^{i - 1} f_{j} - \sum \limits_{j = 0}^{k - 1} f_{j} = \sum \limits_{j = k}^{i - 1} f_{j}.\)
而子序列中相邻两字符在原串中不相同的限制是好保证的，只需要考虑其不同子序列个数的转移方程为 \(f_{i} = \sum \limits_{j = 0}^{i - 2} f_{j}\) 对后面的推导稍作修改即可得到本质不同子序列计数的转移方程为 \(f_{i} = \sum \limits_{j = k - 1}^{i - 2} f_{j}\).
记录一下每个字符 \(c\) 当前最后出现的位置，同时做前缀和优化即可做到 \(\Theta(1)\) 转移。
G
首先可以将 \(q_{i}\) 对 \(p_{i}\) 做置换，将限制转换成 \(r_{i} \not= i, a_{i}\) 的形式。
考虑将 \(i\) 向 \(a_{i}\) 连边，得到若干置换环。这时候问题可以重新描述为“每个点的取值不能为自身权值或后一个点的权值。”
考虑容斥，需要对每个 \(k\) 分别计算“恰有 \(k\) 个点不满足限制的方案数”。容易发现可以对每个环分别计算，于是考虑在一个长度为 \(m\) 的置换环上如何计算。
考虑设 \(f_{i, j, 0/1/2}\) 表示当前考虑到第 \(i\) 个点，前 \(i\) 个点中共有 \(j\) 个点的取值不满足限制，且第 \(i\) 个点的取值为（自身/后一个点/两者皆不）的方案数。转移之前枚举第一个点的取值状态，转移时两个状态之间不能转移当且仅当前一个点的取值为后一个点且后一个点的取值为它自身权值。最后统计方案时判断一下最后一个点的状态能否与枚举的第一个点的状态拼合即可。
将每个环的方案数算出来后只需要每次取两个最小的环使用暴力多项式乘法即可，容易证明时间复杂度是 \(\Theta(n^{2})\) 的。
最后考虑如何计算答案。若设恰好有 \(k\) 个点的取值不满足限制的方案数为 \(g_{k}\)，则根据二项式反演公式，最终答案为：
\[ \sum _ {i = 0} ^ {n} (-1) ^ i \dbinom{n}{i} g_i \times (n - i)! \]其中 \((n - i)!\) 是不满足限制的点的取值确定后，其它点的取值随意排列的方案数。
总时间复杂度 \(\Theta(n^{2})\)。
