A
给定 \(n, m, k\)，需要构造一个数组 \(a\)，使得 \(a_i\) 为 \([1, m]\) 的整数且 \(\sum \gcd(i, i + 1) = k\)
\(n \le 10^5, m \le 10^{12}, n - 1 \le k \le (n - 2)m\)，可以证明有解。
对于这种类型的构造题，结果肯定都是很优美的（要么平均，要么极端）。
这个题考虑每个数都尽量平均的情况，这样只有 \(2\) 种数，比较简单（\(\gcd(x,x) = x\)），而且有一个优秀的性质 \(\gcd(x, x + 1) = 1\)。
不妨设 \(a\) 为 \(y\) 个 \(x + 1\) 和 \(y + 1\) 个 \(x\) 拼接的结果，\(a = x + 1, x+ 1 \dots x + 1, x, x, \dots , x\)。
则 \((y - 1)(x + 1) + (n - y - 1)x + 1 = k\)，化简可得：\((n - 2)x + y = k\)。
为了保证不出现一些奇怪的情况，钦定 \(1 \le y \le n - 1\) 以保证两种数都有。
显然有个解是 \(x = \lfloor \frac{k - 1}{n - 2} \rfloor, y = k - (n - 2)x\)。
时间复杂度：\(O(n)\)。
自己想到的构造是一堆 \(m\) 后面加一堆 \(1\)，但似乎需要调整很多，比较复杂。
构造的方案一定都是比较优雅的，因为有些特殊的性质，这个题也是 。利用 \(\gcd(x, x) = x, \gcd(x, x + 1) = 1\) 刻画出答案，待定一下系数就可以了。
B
\(T \le 100, n \le 10^9\)。
先转化一下 \(y | x + n\)，实际上就是 \(x + n \equiv 0\pmod y\)，\(x\) 是只有 \(y - (n \mod y)\) 一个解（\(y | n\) 没有）。
那么这个图就是一个森林，路径唯一，从 \(x, y\) 往上条找 \(LCA\) 即可。（不然也没什么别的做法。）证明不会，打几个表应该能发现。
C
给定两个长度为 \(n\) 的 \(01\) 串 \(a, b\)，可以进行如下两种操作若干次（选择一个 \(i\)）：
- 花费 \(X\) 的代价交换 \(a_i, a_i + 1\)
- 花费 \(Y\) 的代价将 \(a_i\) 取反。
问将 \(a\) 变成 \(b\) 的最小代价。
\(n \le 10^7, X, Y \le 10^9\)
先只考虑操作 \(1\)，忽略操作 \(2\)。（操作 \(2\) 丢到最后做也是更优的，虽然这个题似乎没啥用。）
将 \(a, b\) 中 \(1\) 的位置取出来，分别记为 \(c, d\)，答案为 \(\sum |c_i - d_i|\)。是一个将 \(1\) 进行匹配的过程。
实际上，匹配操作和取反操作肯定是不交的（天才的想法）。不然设 \(x < i < y\)，\(x, y\) 匹配，\(i\) 取反，将 \(x, i\) 匹配，\(y\) 取反即可，这样更优。
所以两种操作肯定是交替进行的，这就可以 DP 了，令 \(dp_i\) 表示使得前 \(i\) 个位置满足条件的最小代价，那么 \(dp_i\) 可以从 \(dp_{i - 1}\) 转移过来（取反）；也可以从最大的 \(x\)（\(x\) 满足 \(a_{x + 1} \sim a_i\) 与 \(b_{x + 1} \sim b_i\) 的 \(1\) 数量相同）转移过来，这种情况有个性质：要么所有 \(c_i \le d_i\) 要么所有 \(d_i \le c_i\)（否则还可以割开），代价为 \(X(\sum c_i - \sum d_i)\)。
时间复杂度：\(O(n)\)。
“注意到” 匹配和取反操作不交就简单很多了。（怎么想到的呢？可能是因为如果有相交难以计算，先猜测不相交再证明的。）
D
给定一张 \(n\) 个点 \(m\) 条边的无向图，每个点有三个属性：\(a_i, b_i, c_i(b_i \le c_i)\)。
称 \(x\) 能到达 \(y\) 当且仅当存在一条 \(x \rightarrow y\) 的路径满足经过点 \(i\) 时不能有一个前面经过的 \(j\) 满足 \(b_j > c_i\)。
对于每个点，求出其能到达的点中 \({a_i}\) 最大值。
\(n,m \le 2 \times 10^5\)
能否经过 \(i\) 只和 \(b\) 的前缀最大值有关。所以可以将路径按 \(b\) 的前缀最大值分段。
对于每个 \(x\)，都有个“圈子”，里面的点 \(u\) 满足 \(b_u \le b_x \le c_u\)，在这里面的边都可以双向随便走，然后再到达一个 \(v\) 满足 \(b_u \le b_x \le \min(b_v - 1, c_u)\) ，此时前缀最大值就变成了 \(b_v\)，和前面的毫无干系。
而 \(ans_x\) 就是圈子里的 \(\max\{a_u\}\) 以及满足条件的 \(v\) 的 \(ans_v\) 的最大值。
接下来对于每条边 \((u, v)\) 考虑啥时候能成为“圈子”里的无向边（记为 \(1\) 类边），什么时候能成为跨出圈子的有向边（记为 \(2\) 类边）。
- 当 \(\max(b_u, b_v) \le b_x \le \min(c_u, c_v)\) 时是第一种。
- 当 \(b_u \le b_x \le \min(b_v - 1, c_u)\) 时是第二种。
发现对于 \(b_x\) 相同的点整张图是一样的且每条边都对应的是两个区间。
考虑线段树分治，对于 \(1\) 类边，\(u, v\) 是可互相到达的，用并查集维护 \(u\) 所在连通块及里面的 \(a_{\max}\)；对于二种边，\(ans_v\) 可对 \(u\) 所在连通块中所有点进行贡献。然后就做完了。
因为 \(2\) 类边中 \(b_v > r(r 是 b_x 的范围右端点)\)，所以是没问题的。注意要先递归右边再递归左边！！
时间复杂度：\(O(n \log ^ 2 n)\)。
没想到可以对 \(b\) 进行分段（*******），这样每个点的贡献来源就比较清晰了。然后考虑 \((u, v)\) 啥时候为 \(1/2\) 类边，搞个线段树分治即可。