A \((\texttt{Easy} \ 1 / 0)\)
贪心即可。
时间复杂度 \(\mathcal{O}(n)\)。
B \((\texttt{Easy} \ 3 / 0)\)
首先最优的方案肯定是从左往右第 \(i\) 个 \(\texttt{RGB}\) 配对所得的答案。记此时作为最小值和最大值的位置分别为 \(l_1, l_2, \cdots, l_n\) 和 \(r_1, r_2, \cdots, r_n\)。发现一种方案最优当且仅当其中 \(l_i\) 和 \(r_j\) 依然作为一组中的最小值 / 最大值。所以我们考虑给所有在中间的位置选择其左边和右边的数。
下面解决钦定左边的数的情况，右边的情况是类似的。假设一个 \(\texttt{R}\) 被钦定在中间，那么它前面不可能同时出现被钦定在左边的 \(\texttt{G}\) 和 \(\texttt{B}\)，所以它可以选择的数量是确定的，直接乘到答案里即可。
时间复杂度 \(\mathcal{O}(n)\)。
C \((\texttt{Easy} \ 2 / 0)\)
倒着操作，每次取 \(b\) 中的最大值 \(b_i\)，一直减到 \(b_i \le a_i\) 或 \(b_i\) 不是最大值了。如果出现 \(b_i < a_i\) 的情况就寄了。
模拟即可，时间复杂度 \(\mathcal{O}(n \log^2 n)\)。
D \((\texttt{Easy} \ 3 / 1)\)
不难发现第一次操作以后我们需要使得每一列恰好有最终在每一行的元素各一个。
首先考虑确定第一列的数。由 Hall 定理知此时必然存在解，所以跑一个二分图匹配即可。填完第一列之后问题的规模缩小至 \(n' = n, m' = m - 1\)，而条件没有改变，所以依次对于每一列跑二分图匹配即可。
时间复杂度 \(\mathcal{O}(nm^2 \sqrt n)\)。
E \((\texttt{Medium} \ 4 / 2)\)
降智了！
设 \(t = s + s^{R}\)。假设 \(t\) 中存在一段长度为 \(len\) 的子串，其中只包含一个字符 \(c\)，那我们可以使得最终的串的开头 \(2^{k - 1}\) 个字符全部为 \(c\)，此时剩下的字符为这个子串之前长度为 \(n - 2^{k - 1}\) 的子串的翻转。不难发现直接取 \(t\) 中所有长度为 \(n\) 的子串中字典序最小者，然后将其中字典序最小的字符个数乘以 \(2^{k - 1}\)，取它的长度为 \(n\) 的前缀即可。
注意判 \(2^{k - 1} \ge n\) 的情况。时间复杂度 \(\mathcal{O}(n^2)\) 或 \(\mathcal{O}(n \log n)\) 或 \(\mathcal{O}(n)\)。
F \((\texttt{Hard} \ 7 / 4)\)
发现这个条件等价于每次选择把 \(\ge L\) 个连续的 \(x\) 合并成 \(x + 1\)，询问有多少个子区间最后能变成一个数。
首先我们来考虑对于一个固定的区间 \([l, r]\)，该如何判定它合不合法。不妨设 \(l < r\)，区间中的最大值为 \(mx\)，不难发现我们必然需要合成 \(\ge L\) 个 \(mx\)，然后让这些 \(mx\) 合成一个 \(mx + 1\)。我们从小到大合并所有数，为了合并出尽量多的 \(mx\)，我们在合并一段长度为 \(len\) 的数时必然是合并成 \(\left\lfloor \frac{len}{L} \right\rfloor\) 个以减少损失。
于是我们就可以 \(\mathcal{O}(n)\) 地判定一个区间了。不妨枚举区间的最大值，并对整个序列模拟上述过程，假设把所有 \(< x\) 的数合并完成后的序列（可能有若干个序列，因为中间会存在不能合并而寄了的位置把序列一分为二，存在这种情况则依次考虑）为 \(a'\)，则我们枚举 \(a'\) 中所有长度 \(\ge L\) 的 \(x\) 段即可计算答案。但是此时系数就可能不是 \(1\) 了，因为可能有很多个子串能合并至当前的这个 \(x\)。所以我们需要对于每个 \(x\) 去维护有多少个 \(l\) 使得存在一个左端点为 \(l\) 的子串能合成当前段中以 \(x\) 结尾的后缀；以及有多少个 \(r\) 使得存在一个右端点为 \(r\) 的子串能合成当前段中以 \(x\) 结尾的前缀，可以在合并的过程中维护。
不要忘记减去重复计算的贡献以及加上 \(n\) 个长度为 \(1\) 的区间的答案。
时间复杂度 \(\mathcal{O}(n \log n)\)。
标签：子串,复杂度,texttt,mx,最大值,mathcal,AGC037 From： https://www.cnblogs.com/Scintilla/p/16849465.html