A
发现 \(a\) 的线性基的大小很大，枚举一下线性基外面的数选或者不选，判断一下能否构成 \(k\) 个区间即可。
B
我们找出所有的三元组 \((x, y, c)\) 代表某一列中 \(x\) 行和 \(y\) 行颜色都是 \(c\)。
首先三元组的种数只有 \(2n \times (2n - 1) / 2 \times n = n^2 \times (2n - 1)\) 种。
我们接下来证明一列至少会占用 \(n\) 种：
$ \sum c_i = 2n $
\[\begin{aligned} \sum \frac{c_i(c_i - 1)}{2} &= \frac{\sum c_i^2}{2} - \frac{\sum c_i}{2}\\ &\ge \frac{(\sum c_i)^2}{2n} - n\ \text{(Cauchy–Schwarz inequality)}\\ &= n \end{aligned} \]所以 \(m > n \times (2n - 1)\) 时必然无解。
下面给出 \(m = n \times (2n - 1)\) 的构造。
不妨把一对颜色相同的点看作一个匹配，那么如果我们能找出 \(K_{2n}\) 的 \(2n - 1\) 个边集不相交的匹配，每一组匹配都可以循环着染色染 \(n\) 列。
（以下点的下标从 \(0\) 开始）构造匹配是容易的：对 \(i\in [0, 2n - 2]\) 我们找出满足 \(x + y \equiv i \pmod{(2n - 1)}\) 的每一对 \((x, y)\) 根据同余的性质一定有 \(n - 1\) 对，而 \(i \times 2^{-1}\) 一定没有匹配，和 \(2n - 1\) 匹配即可。这样对于每一个 \(i\) 我们都找到了一组匹配，且它们边集不交。
C
首先我们不妨设 \(a_i \le b_i\)。
我们讨论一下一对数 \(a_i, b_i, a_j, b_j\) 的贡献：首先两个都交换的话贡献不变，如果 \(a_i \le b_i \le a_j \le b_j\) 交换了某一组 \((a, b)\) 答案不变，如果 \(a_i \le a_j \le b_i \le b_j\) 交换了某一组 \((a, b)\) 答案加上 \(b_i - a_j\)，如果 \(a_i \le a_j \le b_j \le b_i\) 交换了某一组 \((a, b)\) 答案加上 \(b_j - a_j\)。
概括一下，如果交换了其中一组 \((a,b)\) 那么 \((a_i, b_i)\) 和 \((a_j, b_j)\) 之间的贡献会加上这两条线段的交的大小。
现在问题变成了：给 \(n\) 个线段，每条线段可以染成黑白两种颜色，使每一对异色线段的交的和最大。
我们在数轴上连接 \((a_i, b_i)\)，我们把每个连续段拿出来（类似扫描线那样），如果它被 \((a_i, b_i)\) 这样的边覆盖了 \(k\) 次，那么它的贡献的上界是 \(len \times \left\lceil \frac{k}{2} \right\rceil \times \left\lfloor \frac{k}{2} \right\rfloor\)。
现在通过构造来说明：每个上界都可以达到。
如果一个小段被覆盖了奇数次，那就额外在这个小段左右端点之间连一条边。
这样，每个点的度数都是偶数，它的每个连通块都有欧拉回路。所以被覆盖了 \(k\) 次（包括额外边）的小段会被从左往右走 \(\frac{k}{2}\) 次，从右往左走 \(\frac{k}{2}\) 次。而它只会被额外边覆盖一次，所以把从左往右的染成白色，从右往左的染成黑色，便能达到上界了。
D
先考虑如何求一个串的价值：
首先 \(\texttt{((}\) 之间的贡献和 \(\texttt{))}\) 之间的贡献是好算的。
我们考虑计算出对于长度 \(n\) 的所有合法的括号序列的 \(\texttt{)(}\) 子序列数量，以及原来括号序列的 \(\texttt{()}\) 的子序列数量，那么就很容易算出答案。
此时发现一个串的价值为 \(Ax + B\) 的形式，其中 \(x\) 为该串的 \(\texttt{()}\) 的子序列数量。于是可以对于每一个 \(\texttt{()}\) 都算上贡献，就能做原问题了。
问题变成了如何求长度 \(i\) 的所有合法的括号序列的 \(\texttt{)(}\) 子序列数量和。
设 Catalan 数列为 \(f\)，生成函数为 \(F(x)\)，设答案数列（所有 \(i\) 个左括号的合法括号序的 \(\texttt{)(}\) 子序列的数目之和）为 \(g\)，生成函数为 \(G(x)\)。
考虑合法括号序的构造：在一个合法括号序外加一左一右两个括号，没有贡献；两个合法括号序 \(A,B\) 拼接成 \(AB\)，贡献为 \(\operatorname{len}(A)\times\operatorname{len}(B)\)。
注意到形如 \(ABC\) 的序列只能计算一次，故我们强制钦定只算形如 \(A(B)\) 的括号序，这样多个括号序拼接只会计算最后一次。
考虑递推式为 \(g_i = \sum f_jf_{i - j - 1}j(i - j) + f_jg_{i - j - 1} + f_{i - j - 1}g_j\)。
得到生成函数 \(G(x) = xF^\prime(x)x(xF(x))^\prime + 2xF(x)G(x)\)。
将 \(xF(x)\) 带入 \(\frac{1-\sqrt{1-4x}}{2}\) 得到 \(G(x) = \frac{x^2F^\prime(x)}{1 - 4x}\)。
可以直接线性递推。
而动态维护原序列 \(\texttt{()}\) 数量也是容易的，因为交换 \(x\) 和 \(y\) 两个位置改变量只能是 \(0\) 或者 \(\pm (y - x)\)。
时间复杂度 \(\mathrm{O}(n + q)\)
标签：le,frac,题解,texttt,times,括号,2n From： https://www.cnblogs.com/AC7-/p/16870799.html