A

发现 $\text{lcm}(l,2l) = 2l$，所以当 $r \geq 2l$ 的时候一定有解。

接下来证明 $r < 2l$ 时无解：任意一个数 $x \in [l,r]$，设一个 $y > x$，根据定义有 $\text{lcm}(x,y) > 2x$，所以得证。

B

直接dp。设 $f_{i,j}$ 表示用了 $i$ 次往右，$j$ 次往左的最大收益，一对 $(i,j)$ 可以唯一确定当前的位置，直接转移即可。

C

化简一下条件，发现是两个环：$t_1 = t_3 = t_5 = \ldots$ 和 $t_2 = t_4 = t_6 = t_8 = \ldots$。

发现还有两个额外条件是 $t_1 = t_{n-1}$ 和 $t_2 = t_n$。

那么如果 $n$ 是奇数就会有 $t_2 = t_n = t_{n-2} = t_1$，相当于要求全部字符相等。

如果 $n$ 是偶数就会要求奇数位和偶数位置都相等。

枚举奇数位和偶数位分别是什么数字就行了。

D

看起来就很分类讨论，我们分类讨论线段的相交关系即可。

假设现在有两个线段 $[l_1,r_1]$ 和 $[l_2,r_2]$，设 $f(x)$ 表示操作 $x$ 次能获得的最大的交的长度。

相离

设 $r_1 < l_2$，首先前 $l_2-r_1$ 次操作我们肯定会让 $r_1$ 增加或者是 $l_2$ 减少要不然永远不可能有交，然后我们可以每次花费 $1$ 的代价让交扩大 $1$，但是我们发现当交为 $[l_1,r_2]$ 时我们就只能花费 $2$ 的代价（两个左/右端点同时移动 $1$）来让交增加 $1$ 了，所以

$$ f(x) = \begin{cases} 0,& x \leq l_2-r_1\\ x-(l_2-r_1),&l_2-r_1 < x \leq (l_2-r_1)+(r_2-l_1)\\ r_2-l_1 + \lfloor\frac{x-(l_2-r_1+r_2-l_1)}{2}\rfloor,& x > (l_2-r_1)+(r_2-l_1) \end{cases} $$

相交

这里我们设 $l_1 < l_2$。

其实发现就是相离的情况没有了一开始一段为 $0$ 的情况，类似讨论一下：

$$ f(x) = \begin{cases} x+r_2-l_2,&x \leq r_2-l_1-(r_1-l_2)\\ x+(r_2-l_2)+\lfloor \frac{x-[r_2-l_1-(r_1-l_2)]}{2} \rfloor,& x > r_2-l_1-(r_1-l_2) \end{cases} $$

相含

相交的一种特殊情况。我们设 $l_1 < l_2$，那么线段 $[l_1,r_2]$ 包含线段 $[l_2,r_2]$。

$$ f(x) = \begin{cases} x+r_2-l_2,&x \leq l_2-l_1+r_1-r_2\\ x+r_2-l_2+\lfloor \frac{x-(l_2-l_1+r_1-r_2)}{2}\rfloor,& x > l_2-l_1+r_1-r_2 \end{cases} $$

然后贪心就好了。如果相交或者相含我们可以直接先都选代价为 $1$ 增加 $1$，再选代价为 $2$ 的。

如果相离我们要特判一下是不是不需要操作全部线段：我们把一对线段接起来后就一直用代价 $1$ 操作直到用不了为止，然后再考虑其他线段。

E

发现这个周实际上是个取模，把式子写出来：

$$ \begin{aligned} (x-1)d+y &\equiv (y-1)d+x \pmod w\\ (d-1)x &\equiv (d-1)y \pmod w \end{aligned} $$

这里如果有 $\gcd(w,d-1)=1$ 就可以直接做了，但是很有可能不是 $1$（没有逆元），所以我们考虑提取出 $g=\gcd(w,d-1)$，那么设 $d-1 = kg$，有 $\gcd(k,w) = 1$

$$ \begin{aligned} kgx &\equiv kgy\pmod w\\ gx &\equiv gy \pmod w\\ w &| gx-gy\\ \frac{w}{g}&|x-y \end{aligned} $$

设 $T = \min{m,d}$，如果我们知道了 $x-y=h$，那么 $(x,y)$ 对数就是 $T-h$。设 $c = \frac{w}{g}$，所以答案就是：

$$ \begin{aligned} \sum_{c|h} [h \leq T](T-h) &= T\sum_{c|h}[h \leq T] - \sum_{c | h}[h \leq T]h\\ &= T\lfloor \frac{T}{c} \rfloor-h\sum_{i=1}^{\lfloor \frac{T}{c}\rfloor}i\\ &= T\lfloor \frac{T}{c} \rfloor - h\frac{\lfloor \frac{T}{c} \rfloor(\lfloor \frac{T}{c} \rfloor+1)}{2} \end{aligned} $$

每次询问只需要求 $\gcd $，复杂度 $O(\log T)$。

F

自己的做法

首先离散化。

设 $f_i$ 表示考虑了所有 $r \leq i$ 的线段的答案，设 $w(i,j)$ 表示 $[i,j]$ 中能选出的最多同色线段个数，转移只需要枚举最后一块是同色线段的区间 $[j,i]$：

$$ f_i = \max_{j \leq i} f_{j-1}+w(i,j) $$

$w(i,j)$ 我们可以拆成 $w_1(i,j)$ 和 $w_2(i,j)$ 分别表示线段颜色是 $1$ 和 $2$ 的答案。

我们枚举右端点$r$，每次加入一条颜色为 $t$ 的线段 $[l,r]$ 相当于对于所有 $i \leq l,j \geq r$ 的区间 $w_t(l,r)$ 都加一。我们用线段树维护这个东西，由于是枚举的右端点，只需要让 $[0,i]$ 区间加一就行了。

题解的做法

如果把不能同时选的线段之间连边，答案就是最大独立集。注意到这是一个二分图，所以可以转化为求最大匹配。

于是我们把线段按照右端点排序，维护两个 set 表示待匹配的线段，每次对于一个线段，如果没有颜色不同并且和它相交的线段就把它扔进自己颜色的 set，否则找到和它颜色不同的和它相交的线段中最靠前的一个（贪心匹配），删掉即可。

G

先考虑树的情况：

为了方便讨论我们先取一个特殊点为根。

定义一个点的状态是这个点是饱和点还是非饱和点。如果一个点的子树没有特殊点，那么这个子树一定和这个点的父节点状态一定相同，并且不需要任何花费（只需要子树内父节点向子节点连往下的边即可），也就可以把它们缩起来。所以我们可以默认这个树所有的叶子都是特殊点。

因为要保证根是饱和的，所以每条边只有双向和指向根两种状态。发现缩后的树一个点是饱和点的充要条件是这个点到根的所有边都是双向的，于是题目变成了选择一个包含根的连通块，收益为点权和减去边权和，可以简单 dp 完成后。

思考图怎么做：我们发现一个定理：

一个边双联通分量一定可以通过给边定向变成一个强连通分量

所以把边双缩起来就好了。时间复杂度 $O(n)$。

注意一下这个题需要保证所有叶子都是特殊点这个细节就好了。

注意一下边双递归是存的不是父亲是父亲边防止重边。

注意一下边双求法是在最后判 dfn[x] == low[x]，点双是在每一条边判 low[y] > dfn[x]。就好了。