C

$(i,j)$ 是一个好的对子当且仅当 $i,j$ 所在的连续段不相邻。所以我们相当于在最小化连续段长度，于是考虑按照字母表顺序输出，每次输出一轮当前还剩余的字符各一个，这样一轮一轮地构造，那么连续段长度一定会最短。

D1

容易发现每个序列实际上只要保留 $u,v$ 两个最小的未出现的数。我们发现，用同一个序列操作至多两次，一定可以变成 $v$，而和一个序列操作能得到的值也只有 $u,v$：假如 $x=u$，那么一次就能变成 $v$；否则第一次会变成 $u$，第二次就变成 $v$ 了。

所以我们发现，通过和序列操作得到的最大权值就是 $w=\max v_i$，而且对于任意的 $x$，都可以得到这个结果。所以 $f(x)=\max(w,x)$。分段算一下 $\sum f(x)$ 就做完了。

D2

沿用 D1 的只用保留 $(u,v)$ 的结论，我们不难想到一个建模 $u\to v$，那么对于一个 $x$，可以从 $x$ 开始一直往右走，走得到的数都可以通过序列操作得到。还可以考虑先随便到一个 $u$，然后断掉 $u$ 的任意一条出边，沿着 $u$ 一直往右走。

还有两个特殊 case，显然 $f(x)\ge x$，$\max u_i$ 也是可以随便达到的。

我们像在做 DAG 上 dp 一样，记 $g_u$ 表示 DAG 上从 $u$ 开始往右走最大可以到达的数，初始值 $g_u=u$，由于 $u\to v$ 都满足 $u<v$，所以直接倒序转移就行了，不用拓扑排序之类的。