To_Heart—题集——晚星就像你的眼睛杀人又防火
连一周一更都做不到，只能说自己太颓废了，，。还有一个月了，至少要做到认真考试不睡觉！
1.CFCF814E
link && submission
dp 妙妙题。
首先有个结论是发现这张图的生成是有个性的，首先同层的序号一定相邻，其次除了和父亲的连边外其他的边都是同层的。这引导我们考虑定义 dp 状态。定义 dp[i][j][k] 表示当前层有 \(i\) 个与上一层连了边，上一层有 j 个度数为 2，k 个度数为 3的方案数。然后再定义 f[i][j] 表示考虑到了第 i 个点，最后一层有 j 个点的方案数。答案是 \(\sum\limits_{i=1}^{n-1} f[n][i] * g[0][c[2]][c[3]]\) 其中 c[2] 表示 \([i-j+1,i]\) 中度数为 2 的点的个数。c[3] 同理。然后这个答案的理由是我们只需要看最后一层有多少个点以及其与上一层的连边情况就可以统计出所有的方案数。
2.CF1491H
link && submission
分块随便做咯。有个非常好玩的是这一场是个中国场专门给中国人写了个提示叫来自于 lxl 的 Ynoi。
考虑对序列分块，记录一个数组 Pa[i] 表示在 i 的祖先上出现的第一个和 i 不同块的下标。这样的好处是你可以在 \(\max(B,\frac{n}{B})\) 的复杂度下算 lca，而且你发现这个的修改有一个势能的关系，即每个点被修改了块长次以后它的父亲一定与它不同块。然后随便维护一下就好了。
这道题能学到的是分块LCA，其实和倍增本质差不多，但是这个的好处是平衡了块长？这样暴力修改居然变得优美起来。所以由LCA想到分块LCA的过程才是这类数据结构的启示。
3.AT_agc030_c
link && submission
你们凭什么不来做这道题？啊你们凭什么不来做这道题？？ 算是做过最震撼的构造了。也有可能是我构造本来就做得少
平凡的是 \(k\le 500\) 的部分。可以每一行都放一个相同的数。但是如果说 \(k\) 大于 \(500\) 了呢？
这时候如果还是考虑在原基础上优化，即在每行放相同的基础上放置其他数替换。但是你考虑这个时候每个数周围数的构成。举个例子
1111
2222
3333
4444
对于 1 来说，他的周围是由一个 2 和一个 4 和两个 1 组成。如果我们选择一个 5 来替换 1，那么就有一个 2 和 一个 4 和其他的 2 和 4 不匹配了。如果要改变这种情况就只能把所有的 1 换掉但这样就没有 1 了。
但是这时候你发现对于 1 来说，他斜着相邻的分别为两个 2 和 两个 4。你发现我们有机会更换 \(\frac{k}{2}\) 个 1 来让所有的 2 和 4 匹配。但是什么情况下可以看斜着的呢？就是把图形斜过来！
考虑斜着放。这下我们发现只要在原本放 1 的位置交替放 1 和 5 就可以让矩阵合理，因为你改变一个 1 就会让相邻的两个 2 和 4 变化。
发现这种替换的瓶颈是要求矩阵的长宽是偶数。我们发现 \(n=500\) 刚好是偶数，所以直接在 \(n=500\) 的情况下一直替换就最多能替换到 \(2n\) 个数。
4.CF1693E
link && submission
很早之前的一道遗留题目了。非常清新的数据结构好题。
发现每一个位置值改变成左侧小于他的最大值和右侧小于它的最大值的较小值，那么如果我们从大到小枚举值域，如果一个位置左右比他小的最大值都出现了，那么它的值就会被修改而且贡献加 1。这引导我们将贡献的计算放到左右两边最大值上。
发现每个位置可以有三种状态，分别是 左右两边小于它的最大值均没出现和出现了一边（出现了两边时贡献增加然后状态改为两边均没出现），然后可以发现在从高到低枚举值域修改状态时三种状态所在的位置是一段一段连续出现的，而且一定是中间段未知。考虑每一次修改状态后中间段的改变并以此计算贡献即可。
5.CF1651F
link && submission
首先将恢复挂在两次查询的差上。然后发现每次查询其实就是把一个区间推平，以及有可能把下一个位置的值减小。把这个推平操作看成一个颜色块，那么本质是维护每个颜色块内部的信息。好消息是颜色块个数与 m 同阶，所以颜色块的增减可以暴力。发现每个位置随着 T 的函数是个先增大后不变的函数，于是可以用主席树统计每个颜色块内部经过了 T 秒后哪一块满了不会增加了。这个可以线段树二分做到单 log。
6.ABC292G
link && submission
牛逼题。第一次见这种套路。放篇顶级题解。
重要的是套路的积累，大概是可以把字典序分为当前这一位 [i,j] 是相等的字符从而进行 区间dp。真的好牛逼啊。
7.CF1879F
link && submission
春春挠谭题，啥必 st 表码量题。
首先显然大于 \(\max(a_i)\) 的难度是可以等价在难度等于 \(\max(a_i)\) 的情况中的，所以难度实际上是有限的。这引导我们考虑枚举难度，考虑每个难度剩下来的是哪个以及每个难度对剩下来的那个的答案贡献是多少。发现就是操作次数的最大值所在的人至少能获得次小值的贡献。
对于每个难度 x，每一个人每一条命能坚持的次数是 \(\lceil \frac{a_i}{x} \rceil\)。然后你枚举 x 的时候所有的人可以被划分在 \(\lceil \frac{a_i}{x} \rceil\) 个区间里面，第 i 个区间每一条命能撑的次数就是 i 次。然后根据什么什么性质哦这样分下来从头到尾区间个数有 \(n\ln n\) 个。
首先将所有人按照 \(a_i\) 从小到大排序，那么在枚举 x 的时候被划分再同一个区间的人排完序后一定是相邻的。那么我们只需要使用一种数据结构支持每次 \(\mathrm{O(1)}\) 区间查询 \(h_i\) 的最大值和次大值就行了。然后这个居然可以 st 表？大概的处理方法就是 st表 里面直接放最大值和次大值的下标，如果下标不同那就是不同的两个数，然后分讨比较即可。
8.CF587D
我什么时候过的这个题？哦我抄的题解啊那没事了。
题解，当个知识学习一下。如果要我来说的话前缀优化的本质就是利用前后缀处理重复连边的问题。
9.CF214B
link && submission
嘛，如果不考虑我的错误的话那这道题是没什么错误的。需要学习的是这种处理区间异或第 k 大的方法。大概就是把所有的 \(a_i\) 放在一起在 trie 上查就能做到 nlogn 的复杂度。其他的没什么好讲的。你会了这个剩下的都会了。
10.CF1610G
link && submission
首先肯定是要倒着往前做的，因为如果后面一直有匹配的括号而且前面不变的话是要一直删的。然后你又发现如果要删去一对括号，那么他们内部的括号一定被删完了。我们反过来考虑每次操作。设 dp[i] 表示 考虑到 [i,n] 的字符串的最小方案，根据当前这个括号
是否删除转移。如果要删除那么直到后面第一个和它匹配的括号都要删，所以 \(dp[i]=\min(dp[nxt_i+1],c[i]+dp[i+1])\) 其中 c[i] 表示当前这个字符。
很容易发现转移是棵树。那么你就像倍增LCA的预处理一样处理出来所有的转移就好了。注意判断字符串的大小可以 hash。
记录一下最后一步，这种处理很牛逼的。