seerc2021

A

比较字符串的字典序可以进行贪心，所以用一个指针从前往后扫描，维护一个计数器，对于当前字符，如果两个串相同则可以累加计数器，否则若字典序较小，则统计答案，合法的区间左端点个数为计数器累加的数，右端点个数为右边剩下的数，若字典序较大，则清空计数器，因为以后的都不满足题意。

B

不难发现加的操作可以直接使用可持久化线段树维护，对于区间覆盖来说不太好弄，因为区间覆盖后无法很好的维护列，考虑列实际上很少，以及可持久化线段树具有很好的合并功能，所以对于每种可能的合并情况都使用线段树进行维护，如果区间覆盖就直接在没有这一列的情况下加入即可。

C

容易想到一个看上去时间复杂度很假的做法，枚举颜色，然后做树上背包，实际上用到一个结论，在树上归并时，如果限制子树大小为 $k$，那么最终的时间复杂度是 $O(nk)$，这样的话最后时间复杂度为 $O(n^2)$ 。

下面证明这个结论，有两种方法理解。

方法一，考虑将两个联通块归并时，这两个连通块的大小，第一种，都大于 $k$，那么归并一次的时间复杂度是 $O(k^2)$，归并次数不超过 $O(\frac{n}{k})$，第二种，仅有一个大于 $k$，那么每归并一次就会少一个小于 $k$ 的连通块，这样也是 $nk$，第三种，都小于 $k$，这样可以先合并出若干个大于 $k$ 的联通块，每个连通块消耗 $k^2$ ，最多 $\frac{n}{k}$ 个块。

方法二，归并时强行假设枚举的点对是 dfn 序最接近的 $2k$ 个点，这样点对中两个点的 dfn 序差不超过 $2k$，最后得到的点对是 $nk$ 级别的。

E

首先 $B$ 数组的顺序是不影响最终结果的，于是先将 $B$ 数组排序方便处理，不难发现我只需要知道前一个数是多少就能够对当前数进行决策，而前一个数最多只有 $m+1$ 种情况，得到一个 $N^2$ 的算法，定义 $dp[i][j]$ 表示当前考虑到第 $i$ 个位置，这个位置上放 $b_j$ 的最小步数，若 $j$ 为 $0$，则表示不替换，转移只有如下几种情况，当 $a_i>a_{i-1}$ 时，$dp[i][0]=min(dp[i][0],dp[i-1][0])$，当 $a_i<a_{i-1} $时，对于所有满足 $b_j>a_{i-1}$ ，$dp[i][j]=min(dp[i][j],dp[i-1][0]+1)$，对于所有情况，$dp[i][0]$ 和所有比它小的 $b_j$ 取 $dp[i-1][j]$ 的最小值，对于 $dp[i][j]$ 的更新，采用贪心策略，$dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1)$，这样做是因为如果当前放 $b_j$ ，那么前面放 $b_{j-1}$ 一定不劣，这样做是 $N^2$ 的，考虑优化，发现可以将不替换的单独拿出来考虑，这个时间复杂度可以接受，只需要考虑替换时怎么维护 $dp$ 值，发现需要做的只有将整个数组平移一个单位和区间对一个数取 $min$ ，使用吉司机线段树维护即可。

F

不难发现如果要使用毒药，那么一定是在最开始用了若干瓶，然后又去抵消了一个前缀的回复效果，只需要枚举这个前缀是多少然后计算最优情况即可。

G

因为 $w$ 和最终答案的和都是求最大值，所以可以直接去掉绝对值，这样相当于给 $n$ 个数负号，$n$ 个数正号，使得和最大，显然，负号会给到数对中的较小值，正号会给到数对中的较大值，考虑什么时候给正号比给负号优，设第一对给了正号，第二对给了负号，那么给第二对正号更优当且仅当 $a_1-b_2<a_2-b_1$，发现按照 $a+b$ 排序然后取前 $n$ 个即可。

J

根据 $A,B,C$ 的数量，我们可以求出 $AB,BC,AC$ 各自有多少个，以 $AB$ 为例，它有 $\frac{cnt_A+cnt_B-cnt_C}{2}$ 个，由于 $B$ 的前面也能接，后面也能接，所以我们优先处理 $B$，如果存在划分方案，那么将 $B$ 的前 $cnt_{BC}$ 个和 $C$ 配对，$B$ 的后 $cnt_{AB}$ 个和 $A$ 配对，这样一定是不劣的，考虑 $AB$ 中用到的 $A$ ，应该是距离 $B$ 最近的 $A$ ，$BC$ 同理，这样剩下的 $AC$ 一定可以配对，否则不存在划分方案。

K

如果根确定，那这题十分显然，只需要根据叶子节点的大小去搜索即可。

现在问题转化为如何确定根，考虑对于一个结点来说，它要么作为根，要么有一个父亲，考虑与这个点相邻的若干块中，影响这个点的只有最小的叶子最大的那个块，比较这个叶子和当前点谁放在序列上更优即可。

具体实现可以从最小的叶子结点开始往上找根，然后依次更新答案。

L

实际上最多只要两次即可实现，只需要找到一个前缀，让它恰好包含一种字符出现了 $n$ 次，将后面区间分成两段分别覆盖一种字符即可，于是依次判断能否用 $0,1$ 次来实现这个问题，$0$ 次直接判断，$1$ 次用双指针即可。

N

考虑对 $a$ 数组操作不太好弄，因为不一定每一个 $a_i$ 都会向下产生贡献，而 $b_i$ 则不是，如果存在 $b_i$，那么它一定是需要被抵消的，所以每次将 $b$ 数组往上推即可。