A：

我们考虑一个产生贡献的 $1 \times 1$ 矩形是由一个字符的 $\uparrow$ 和另一个字符的 $\rightarrow$ 构成的。

于是我们可以先预处理一个字符变成 $\uparrow$，另一个字符变成 $\rightarrow$ 构成的面积，最后枚举每个字符的变化情况可以算出答案。

实现精细下可以做到 $\mathcal O\left(T\left(n+2^{m}\right) m\right)$ 。

B：

将二元组 $\left(a_{i}, b_{i}\right)$ 看成线段 $\left[b_{i}+1, a_{i}\right]$ ，可以得出以下结论：

• 两个二元组反二维偏序等价于转换后的线段有交（有交的意思是至少共同包含一个点）。
• 区间合法等价于对于区间中的所有线段，若把有交的线段连接一条边，则每一个连通块的线段都必须两两有交。

我们考虑双指针的过程，考虑加入一条线段 $[l, r]$ 判定合法。

我们找到与 $[l, r]$ 连通的线段的最小左端点 $L$ ，与 $[l, r]$ 连通的最大右端点 $R$ ，显然，被 $[L, R]$ 包含的线段等价于跟 $[l, r]$ 连通的线段。

加入合法当且仅当 $[l, r]$ 内存在一个点使得被 $[L, R]$ 中所有线段包含，即 $[l, r]$ 中线段个数最大值等于 $[L, R]$ 线段个数。

使用线段树维护区间加求区间最大值，使用线段树维护区间加求前驱后继，使用树状数组维护单点加区间和，复杂度 $\mathcal O(T n \log n)$ ，常数较小。

C：

题目名字叫：

定义状态 $dp[u][x \rightarrow v]$ ，其中 $u$ 是第一个树的结点， $x \rightarrow v$ 是第二个树的有向边，用来表示是否可以匹配结点 $u$ 和 $v$ ，同时将结点 $u$ 的子树匹配到结点 $v$ 的子树，如果第二个树以 $x$ 为根结点。

通过这种方式，它匹配了边 $p(u) \rightarrow u$ 和 $x \rightarrow v$ 。

然而，这种动态规划计算速度较慢，考虑缩减状态：

不计算所有形式为 $dp[u][x \rightarrow v]$ 的状态，而是一次只对一对结点 $(u, v)$ 运行一次匹配。

如果找到了覆盖左部分的匹配，就做完了；

如果无法覆盖至少 2 个结点，则所有 $dp[u][x \rightarrow v]$ 的值为 0；

如果除了一个结点外都能覆盖所有结点，则从该结点运行一次 dfs，沿着任何边向右走，只沿着匹配中的边向左走，这样就可以找到所有 $dp[u][x \rightarrow v]=t r u e$ 的结点 $x$ 。

这种解决方案的时间复杂度是 $\mathcal O\left(n m^{2}\right)$ ，其中 $n$ 是结点数， $m$ 是边数。

使用 Dinic 算法，时间复杂度是 $\mathcal O(n m \sqrt{m})$ 。

D：

我们从小到大枚举 $r$ ，并对于每个左端点维护 $\operatorname{mex}\left(a_{l . . r}\right)$ （下面记为 $\left.\operatorname{mex}(l, r)\right)$ 。这个显然是随着 $l$ 的递减而单调不降的。

我们考虑新加入 $a_{r+1}$ ，并从 $r$ 的信息转移到 $r+1$ 的信息。

考虑是否存在一段区间 $\left[l^{\prime}, r^{\prime}\right]$ 满足所有 $i \in\left[l^{\prime}, r^{\prime}\right], \operatorname{mex}(i, r)$ 都相等。如果不存在，那么新加入一个数后，之前的 mex 都不会变。

如果存在，则这段中的 mex 都会变大。

我们考虑把这样的段都找出来，每次删掉一个段，插入若干段。由于任意时刻，段数最多只有 $n$ ，所以总共插入的段数是 $O(n)$ 。

用线段树维护每个值最后一次出现的位置，那么所有段的开头就可以在线段树上 dfs 得到。

dfs 的总时间复杂度 $\mathcal O(n)$ 。

我们发现，每次相当于增加了 $\left[l^{\prime}, r^{\prime}\right]$ 对 $[l, r]$ 的贡献。由于每个值域的贡献是不交的，我们对每个值域维护一条扫描线即可。

由于题目要求强制在线，我们用可持久化线段树维护扫描线即可。

时间复杂度 $\mathcal O(n \log n)$ 。