2025/9/10 | 2025CSP-S模拟赛57
https://oj.gxyzh.com/d/hzoj/contest/68d921a11bde45b9248e2bb9/problems
国庆第一天训练。初三牲要死了。搬到机构里训练，效率几乎为零。
T1其实是简单题。但是考场上想了AB性质后就没有想法了，就是把这串数的最终结果求出来，然后给每个原数匹配一个最终数。答案是每个数的增加量乘bi的一种排列的最小值。当时也想到了增加量最大的匹配小的bi的。但是因为一些原因不能直接简单地将原数和最终数匹配（比如必须满足最终数大于等于原数）例如原数列为1 2 2 5，最终数列为1 2 3 5，显然就不能直接将1和5匹配，这样子最后一个5就没的匹配了。
所以我们考虑换个思路 从大到小匹配，在最终数列里面找到第一个大于等于当前数的数字即可。这样就能满足要求了。
T2，当时写了个O(n2)的dp（真的应该是严格的n2啊），但是只能获得O(n^3)的30pts，非常气愤却无果。正解首先是要观察到一个性质，就是最终划分的mex只有一种，这个mex就是全局的mex。证明不说了。然后原来那个dp式子就能写的很简单了。设dp[i]表示以i结尾的划分方案数，如果能满足mex[j][i]等于全局的mex i就能从j转移过来，然后会发现能转移过来的j一定是一段前缀（因为全局的mex一定是大于等于局部的mex的），而且这个前缀也是单调不降的。用单指针求出每个i对应的最右边的j，转移用前缀和优化即可。
T3感觉是很神奇的一道题，它需要用到一个知识点：Kruscal重构树，因为这个树有一个性质就是，任意两点的lca就是他们原图中路径上最大边权最小值。但是我学到的这种解法非常简单直白啊（我总感觉它并不是真正意义上的Kruscal重构树），就是建两棵树，满足如果i是j的祖先i就一定是i到j这条路径上的最大/最小值，然后两棵树各跑一遍，统计在第一棵树里i是j的祖先且在1第二棵树里j是i的祖先的对数即可。