CF1884
2C
假设咱们钦定在 \(x\) 处取到最大值，则对于任意线段 \(i\)，若 \(i\) 覆盖点 \(x\)，则选中她会使得 \(\max a \leftarrow \max a + 1\)，\(\min a \leftarrow \min a + y\)，\(y \in \{0, 1\}\)，则对答案产生 \(\ge 0\) 的贡献，故此时必然将所有线段 \(i\) 均选中。
接下来咱们考虑在确定最大值于 \(x\) 处取到后，此时被覆盖次数最少的点在何处取到：令 \(f_i\) 表示点 \(i\) 被多少个线段覆盖，则可知 \(f\) 随 \(i\) 先单调不降再单调不升（证明：在 \(x\) 前，每经过一个左端点则 \(f_i \leftarrow f_{i - 1} + 1\)；在 \(x\) 后，每经过一个右端点则 \(f_i \leftarrow f_{i - 1} - 1\)），故此时最小值必然于 \(1\) 或 \(m\) 处取到。
覆盖 \(1\) 的线段个数 \(= \#\{i | l_i = 1\}\)，覆盖 \(m\) 的线段个数 \(= \#\{i | r_i = m\}\)，扫描线维护即可。
2D
直接求数对 \((i, j)\) 的个数不是很好求，考虑反过来，求不满足条件的数对 \((i, j)\) 的个数，此时存在 \(k\)，使得 \(a_k | a_i\) 且 \(a_k | a_j\)，即 \(a_k | \gcd(a_i, a_j)\)。
咱们令 \(f_x\) 表示满足 \(\gcd(a_i, a_j) = x\) 的数对 \((i, j)\) 个数，\(c_x\) 表示数列 \(\{a_i\}\) 中 \(x\) 出现的个数，则有：
\[\binom{\sum_{p \in \mathrm{N}, px \le \max a} c_{px}}{2} = \sum_{p \in \mathrm{N}, px \le \max a} f_{px} \]因此咱们有：
\[f_x = \binom{\sum_{p \in \mathrm{N}, px \le \max a} c_{px}}{2} - \sum_{p \in \mathrm{N}, p > 1, px \le \max a} f_{px} \]咱们记集合 \(S\) 为 \(a_k\) 的倍数集合，答案为 \(\binom{n}{2} - \sum_{i \in S} f_i\)，单次转移 \(O(\frac{\max a}{x})\)，总复杂度 \(O(\max a \log \max a)\)，\(n \ge \max a\)。
CF1886
2C
咱们假设钦定 \(s\) 前 \(i\) 位保留，删除第 \(i + 1\) 位，假设存在一个 \(j < i + 1\)，使得 \(c_j > c_{j + 1}\)，则删除 \(j\) 比删除 \(i + 1\) 优，故必然在第一个 \(i\) 满足 \(s_i > s_{i + 1}\) 的位置删除，链表维护第 \(i\) 个点的前后继即可。
2D
考虑倒着做 \(s\) 的构造，对于 \(\texttt{>}\) 相当于移除 \(s\) 中的最大元素，\(\texttt{<}\) 相当于移除 \(s\) 中的最小元素，\(\texttt{?}\) 相当于移除 \(s\) 中非最大也非最小的数。对于 \(s_i\)，其中共有 \(i + 1\) 个元素，故最终答案即为 \(\prod_{s_i = \texttt{?}} (i - 1)\)。
2E
「CSP 2019 划分」的精神赓续！
形式化题意：给定序列 \(a\)，要求用 \(m\) 个集合覆盖序列的元素，使得每个集合至少覆盖住一个元素，且这些集合两两无交，并且对于每个集合 \(S_i\)，其所覆盖住的每个元素 \(a_k\) 都有：\(a_k \ge \frac{b_i}{|S_i|}\)。
首先咱们对序列 \(a\) 做有序化处理，使得其单调不增，即始终有 \(a_i \ge a_{i + 1}\)，咱们假设对于集合 \(S_i\)，其覆盖住的最小元素为 \(a_{j_0}\)，其覆盖住的所有元素为 \(\{a_{j_0}, a_{j_1}, \cdots, a_{j_{p - 1}}\}\)，对于 \(a_{j_0 + q}, q \in [1, p - 1]\)，若覆盖住它的集合为 \(S_r\)，则将 \(a_{j_0 + q}\) 移入 \(S_i\)，将 \(a_{j_q}\) 移入 \(S_r\)，显然 \(a_{j_q} \ge a_{j_0 + q}\)，则移动后 \(|S_i|\) 与 \(|S_r|\) 均不变，显然 \(S_r\) 仍满足条件，又因为 \(a_{j_0 + q} \ge a_{j_0} \ge \frac{b_i}{|S_i|}\)，故 \(S_i\) 亦满足条件，咱们立即得出推论：必然存在一个解，其每个集合均覆盖住一段区间。
接下来咱们注意到：假设集合 \(S'\) 是所有集合中所覆盖住的区间左端点最小的集合，若其左端点不为 \(1\)，则将 \(1\) 到 \(S'\) 左端点的元素全部并入 \(S'\)，此时 \(|S'|\) 增大，故 \(\frac{b'}{|S'|}\) 减小，则此时 \(S'\) 仍满足条件，故咱们又得到一个推论：必然存在一个解，其最左端的区间（集合）的左端点为 \(1\)。
咱们又注意到，上述的推论自然地带有数学归纳的特征，因为将最左端的区间所覆盖住的元素从原序列中移除后，就形成了一个新的序列，且移除的元素不对后续产生任何约束，则由数学归纳法立即得出：\(S_1 = [1, r_1], S_2 = [r_1 + 1, r_2], S_3 = [r_2 + 1, r_3], \cdots, S_t = [r_{t - 1} + 1, r_t]\)，此时问题转化为：构造序列 \(\{r_1, r_2, \cdots, r_t\}\)，其严格单调增，且 \(r_1 \ge 1, r_t \le n\)，并满足条件：\(\forall i \in [1, t], a_{r_i} \ge \frac{b_i}{r_i - r_{i - 1}}\)（\(r_0 = 0\)）。
现在咱们可以记 \(f_{i, S} \in \{0, 1\}\) 表示已经处理了前 \(i\) 个 \(a\) 的元素，目前已经完成对集合 \(S\) 中的所有集合的分配（均分配了一个 \([1, i]\) 的子区间），并且 \(i\) 作为其中一个集合的右端点时能否对 \(S\) 中的所有集合完成其对应的 \(r\) 的构造，很显然有转移：\(f_{i, S} \rightarrow f_{j, S \cup \{k\}}, k \notin S, a_{j} \ge \frac{b_k}{j - i}\)。
但是这个东西非常蠢！咱们考虑经典值域定义域互换：咱们注意到，如果对于所有可行构造 \(\{r_1, r_2, \cdots, r_t\}\) 中 \(r_1\) 的最小值为 \(r_1'\)，则将任意一个可行构造中的 \(r_1\) 换成 \(r_1'\) 后构造仍可行。故咱们直接令 \(f_S\) 表示对 \(S\) 中的所有集合均分配完其对应的 \(r\)，此时 \(S\) 中的所有集合所覆盖的元素形成的前缀长度的最小值，考虑 \(f_S\) 如何转移：令 \(R(i, j)\) 表示令 \(i\) 作为第 \(j\) 个集合所覆盖区间的左端点，其最小的右端点 \(r\)，则有：
\[f_S = \min_{k \in S} R(f_{S - \{k\}} + 1, k) \]有解当且仅当 \(f_U \le n\)，\(U = [1, n]\)，\(r\) 的构造也可以直接根据 \(f\) 的转移得出，同时 \(R\) 可以利用其在 \(j\) 确定时的不降性将复杂度均摊掉，\(O(nm + m2^m)\)。
标签：覆盖住,max,px,CF,ge,随机,端点,集合 From： https://www.cnblogs.com/Reimu-Hakurei/p/17806186.html