A
给定 \(n\) 个区间 \([a_i, b_i]\)。若将所有有交集的区间合并，最后有多少区间。
按 \(a_i\) 排序。记录当前正在尝试合并的区间的左右端点 \(l, r\)。初始 \(l = a_1, r = b_1\)。
枚举 \(i = (2, 3, \dots, b)\)。此时：
- 如果 \(r \ge a_i\)：合并。实现上就是 \(l\) 不变，\(r \gets \max(r, b_i)\)。
- 如果 \(r < a_i\)：重开。实现上就是 \(l \gets a_i\)，\(r \gets b_i\)。
B
给定 \(n\) 个区间 \([a_i, b_i]\)。
给定 \(m\) 个人，每个人有一个区间 \([c_i, d_i]\) 和 \(k_i\)。
如果 \([a_i, b_i]\) 被 \([c_j, d_j]\) 包含，那么第 \(j\) 个人就可以选择区间 \(i\)。
每个区间至多被一个人选择，每个人至多选 \(k_i\) 个区间。
求是否所有区间都能被某个人选中。
把区间和人放在一起，并全部以左端点排序。左端点相同时把人排在前面。
然后按顺序枚举 \(i = (1, 2, \dots, n + m)\)。如果第 \(i\) 个是区间，那么我们需要找到一个人 \(j\) 且满足：
- \(a_j \le c_i\)；
- \(b_j \ge d_i\)。
由于我们是按 \(a, c\) 排序的，所以第一个条件即 \(j < i\)。问题也就变成了要在 \(i\) 之前找到一个人 \(j\)，且人的右端点在区间的右端点的右面。
此时如果有多个满足条件的人，那么我们应该贪心地找右端点最小的，也就是找 \(b_j\) 最小的。
实现上维护 set。枚举到人时加入 \((d_i, k_i)\)。枚举到区间时找到最小的大于等于 \(b_i\) 的 \(d_j\)，并将 \(k_j\) 减一。如果 \(k_j = 0\) 将其移除 set。
C
给定长度为 \(n\) 的序列 \(a\)。
对于一个 \(x\)，选择 \(a_i\) 的代价为 \(|a_i - x|\)。
给定代价之和的上限 \(B\)。求一个 \(x\)，使得选择的 \(a_i\) 最多。
可以发现，如果将 \(a\) 从小到大排序，那么最终选择的 \(a_i\) 一定是连续的。
若确定了区间 \([l, r]\)，那么代价之和为 \(f(l, r) = \sum_{i = l}^r |a_i - x|\)。很显然将 \(x\) 确定为这些数的中位数 \(f(l, r)\) 最小。
枚举左端点 \(l\)。此时需要找到最大的 \(r\) 满足 \(f(l, r) \le B\)。此时可以 \(\mathcal O(n \log n)\) 二分做。
同时可以发现随着 \(l\) 变大，\(r\) 一定不会变小。所以可以 \(\mathcal O(n)\) 双指针。
D
给定长度为 \(n\) 的序列 \(a\)。
至多 \(m\) 次操作，每次可以将一个大于 \(0\) 的 \(a_i\) 减一。
你需要进行若干次操作后，使得存在 \(a_k = 0\)，且 \(\max(|a_i - a_{i + 1}|)\) 最小。
求这个最小值。
二分答案 \(x\)。然后求在不一定存在 \(a_k = 0\) 的条件，所有的 \(|a_i - a_{i + 1}|\) 都小于等于 \(x\) 的最小操作次数。
先从左往右调整 \(a_i \gets \min(a_i, a_{i - 1} + x)\)。然后还会有不满足的，于是再从右往左调整 \(a_i \gets \min(a_i, a_{i + 1} + x)\)。记录操作次数。
然后枚举 \(k = (1, 2, \dots, n)\) 表示将 \(a_k \gets 0\)。那么序列会变成这样：
\[a_1, \cdots, l \times x, \cdots, 2x, x, 0, x, 2x ,\cdots, r \times x, \cdots, a_n \]也就是说在 \(a_k\) 出形成了一个辐射状的等差数列，这个等差数列往左延申到 \(k - l\)，往右延申到 \(k + r\)。
可以发现随着 \(k\) 的递增，\(k - l\) 和 \(k + r\) 都不会变小。所以还是双指针。
E
给定 \(n\) 个区间 \([a_i, b_i]\)。
你需要选择 \(m\) 个区间，使得它们至少有一个公共点且区间长度的极差最小。
如果有若干个区间被选中，那么如果其中有 \(m\) 个区间有至少一个公共点，就代表如果将每个区间内的位置加 \(1\) 的话存在一个位置大于等于 \(m\)。
我们首先按照区间长度从小到大排序。然后枚举最小长度 \(l\)，找到最大长度 \(r\)，使得将 \(l \sim r\) 这些区间按照上述操作加一后存在一个位置大于等于 \(m\)。那么此时 \(r - l\) 即为答案。
找这个 \(r\) 可以二分做。同时观察到，随着 \(l\) 变大，\(r\) 一定不会变小。所以 \(\mathcal O(n)\) 双指针。
F
给定长度为 \(n\) 的仅含 \(\texttt {ab}\) 的字符串。
你可以改变至多 \(k\) 个字符，求改变后最大的连续相同字符的数量。
二分答案 \(x\)。要做的就是判断是否存在一个长度为 \(x\) 的区间，使得能够在进行不超过 \(k\) 次的情况下，将其变成相同的。于是统计区间内 \(\texttt{ab}\) 字符分别数显的次数，然后与 \(k\) 比大小即可。
也可以双指针。假设我们要全变成 \(\texttt{a}\)，那么仍然是维护两个指针 \(l, r\)，表示 \(l \sim r\) 中 \(\texttt b\) 的数量不超过 \(k\)。于是找到最大的 \(r\) 然后计算最大长度 \(r - l + 1\) 即可。
G
给定长度为 \(n\) 的序列 \(a\)。
定义 \(f(l, r)\) 表示区间 \([l, r]\) 内不同元素的数量。
随机选取 \(l, r\)，求 \(f(l, r)\) 的期望。
一个区间内相同的元素只会对答案产生一次贡献。不妨将这次贡献放在最左面的元素上。
考虑这个问题：第 \(i\) 个元素上一次出现在 \(j\) 的位置，有多少个区间 \([l, r]\) 是 \(i\) 元素可以贡献的？
显然需要满足两个条件：
- \(j < l \le i\)；
- \(i \le r \le n\)。
那么答案即 \((i - j) \times (n - i + 1)\)。
于是统计每个元素在它之前最后一次出现的位置。然后根据上述公式累加答案即可。