2025多校CSP模拟赛2
狂写大树套树通过 \(T3\) 的救赎感。
T1 查询
第一眼感觉不好做。
首先直接找绝对没前途，考虑二分 \(v\)。
问题变成了统计 \(a_j+b_j\times c_i\le v\) 的数量，变换一下变成：
发现可以更换为向下取整，那么对于每个 \(c_i\) 直接二分找到所有合法点对即可。
复杂度 \(O(n\log n\log V)\)
T2 参加
写了一个迷幻代码，挂了。
本来没觉得赛时代码能过样例，但是过了，就没管了。
发现区间加可以变为差分上两个点一个加一个减，那么答案就是加法和减法的 \(max\)。
那么直接 \(dp\)（其实没必要）。
枚举作为中间点的是哪个，然后求出让左边差分全部变为正的代价，和右边全部变为负的代价，取个 \(max\) 就好了。
复杂度 \(O(n)\)
T3 决斗
比较神秘的题。
首先随意求出一个方案是显然的，那么如果我们以位置从小到大构造最优答案，其实就已经包含了一个性质就是得分点不可能在变为失分点。
所以可以对于每个位置向后找到每个使得交换两个位置的卡牌不影响得分的位置，那么在这些位置中找到最大的一个交换即可，可以证明是正确的。
这样就做出了一个 \(O(n^2)\) 的做法。
考虑怎么优化，先分讨当前点的得分情况。
设 \(a_i\) 表示柯南出的牌，\(pos_i\) 表示青蛙出的牌。
钦定 \(pos_j\ge pos_i\) 不然一定不优。
\(a_i < pos_i\) 得分
此时 \(a_i < pos_j\) 那么也会得一分。
那么如果 \(j\) 不得分，则可以任意选取。
如果 \(a_j < pos_j\) 此时要满足 \(a_j < pos_i\) 。
\(a_i \ge pos_i\) 不得分
如果 \(j\) 也不得分，那么可以随意选取。
否则分为两种情况：
- \(a_j\ge pos_i,pos_j>a_i\)
- \(a_j<pos_i,pos_j\le a_i\)
如果将 \((a_i,pos_i)\) 看做一个点，那么问题竟然变成了二维数点问题！
直接上树套树就做完了。
代码并不好写，应该没人想这么写......
T4 回文串问题
好题。
首先假设所有数不相等，将回文串拼在原序列后面，发现相等关系构成了 \(n\) 个等价类，那么只可能有 \(n-1\) 次合并。
如果此时我们只合并有意义的修改，那么复杂度就有保证了。
那么可以使用二分哈希找到所有不相等的地方，用一个数据结构维护一下就好。
然后等价类间的合并可以使用启发式合并，这样复杂度就是 \(O(n\log^2n)\)。