一些炼石题单
strcmp
·
·
个人记录
记录一下最近关于梦熊炼石做的题。
维护 \text{pre}，查询是区间 \min，扫描线即可。
最值分治启发式分裂，\Theta(n \log n)。
找到所有 1 的位置，讨论一个 p 跟相邻的 1 配对的区间是否合法即可，区间合法性判断是简单随机化 Sum Hashing。复杂度 \Theta(n)。
写出转移式后，将序列按 \bmod k 分组，转移式是决策来自上一层 +a_i 还是直接来自上一个位置，不难发现只有 a_i \ne a_{i - 1} 的时候该决策才有意义，然后是一段区间覆盖。这里我没想到怎么规避线段树上二分，总之线段树上二分肯定能做。对于 a_i 段很长的情况，记录全局加了多少次即可。时间复杂度 \Theta(n \log n)。
不同颜色之间显然相互独立，将每种颜色的箱子和钥匙单独建立虚树，对于每个钥匙，dfs 就近求出能和其产生的贡献的箱子，问题转化为查询树链覆盖了多少个已知树链，转 dfn 就是矩形加单点查。
- P4220 [WC2018] 通道
对第一棵树边分治在第二棵树上建立虚树，在第二棵虚树上枚举 LCA，然后大概是在第三棵树上找到 $v$ 子树内点集合的直径端点，跟 $u$ 前面做完的子树的直径端点合并。
对虚树归并排序，$\Theta(n \log n)$。
- P5327 [ZJOI2019] 语言
现在已经变成套路题了。
不难发现我们本质上是求经过点 $u$ 的 $s_i,\,t_i$ 构成的链并，经典结论，以 dfn 为下标，树上差分线段树合并维护链并大小即可。
$\Theta(n \log n)$。
- [CEOI 2019] Dynamic Diameter
欧拉序动态直径板子。
具体来说我们发现 $[e_l,\,e_r]$ 中间的深度最小值就是它们的 LCA，维护两边深度最大值减去 $2 \times$ 深度最小值的最大值即可，这是线段树可维护的。
改边权是区间加，这是容易的。
$\Theta(n \log n)$。
- P8860 动态图连通性
处理出 $t_i$ 代表 $i$ 边删除的时刻，我们需要求出一个最小的 $t_i$ 尽可能大的路径，排序 $t$ 后是比较字典序，其它边都可以被删，这个路径删不了。主席树做比较字典序即可。$\Theta(n \log^2 n)$。
基于这个有个贪心做法，$\Theta(n \log n)$。
- P5321 [BJOI2019] 送别
正常做法就是纯种大份题，不想做（建议学 A_zjzj 做法orz）
。
- P9494「SFCOI-3」进行一个走的行
离线下来扫描线，倍增值域分块套 fhq 即可。
平衡树有交合并是什么做法。
$\Theta(n \log^2 n)$。
**补充题单**
- HDU7530 树上询问
Check 一条路径是简单 Xor Hashing，然后放到点分树上，以子树为信息维护最小最大值及出现次数 Check $[l,\,r]$ 是不是在两个以下的子树内，然后就能找到对应子树，对每个子树维护平衡树查询 $[l,\,r]$ 内离根最远的点即可。
$\Theta(n \log^2 n)$。
大概率做复杂了吧。
- HDU7505 纠缠点对
两条路径有交，当且仅当一条路径的 LCA 在另一条路径上。
离线下来把路径挂到 LCA 上，考虑枚举深度小的那个 LCA，考虑 dsu on tree，先枚举另一个 LCA 在轻子树内的情况，这可以直接暴力，做完后递归，另一个 LCA 在重子树内是简单二维数点。
$\Theta(n \log^2 n)$。
塞了一堆 NOIP 原题，不放了。
- QOJ2554 AND PLUS OR
令 `x = i & j, y = i - (i & j), z = j - (i & j)`，问题转化为 $a_{x + y} + a_{x + z} < a_x + a_{x + y + z}$，即 $a_{x + y} - a_x < a_{x + y + z} - a_{x + z}$。只要存在一个 $z$ 满足条件，则根据类似介值定理的推论，我们一定有一种方法一个个填 $z$ 的某一位，某一刻满足条件。注意到 $y$ 跟 $z$ 本质相同，$\Theta(n^2 2^n)$。
- QOJ4808 Great Party
某次正睿的 T1。
首先 $n = 1$ 先手当然必胜。
考虑 $n = 2$，不难发现谁合并谁输，所以都不会合并。双方最后会拖到剩下两个 $1$ 的情况，这是 $a_i - 1$ 的 nim。
然后 $n = 3$，我们无论如何都有方法使得剩下的两个数异或和为 $0$。
然后可以猜测奇数区间必胜，偶数 $a_i - 1$ nim。
那么可以莫队维护，$\Theta(n \sqrt n)$。
很严谨的证明似乎没那么容易。
- QOJ4802 Ternary Search
分开山峰和山谷，当只考虑山谷的时候，先计算一个数必须的代价。计算完后，当一个数从右边移动到左边，那么其代价是固定的（它为右端点的逆序对数），我们记录这个代价，加入一个数的时候是后缀减，取出全局为 $0$ 的数放到左边。
$\Theta(n \log n)$。