一些炼石题单

记录一下最近关于梦熊炼石做的题。

维护 $\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 就是矩形加单点查。

$\Theta(n \log n)$，不知道为什么被卡常了。

对第一棵树边分治在第二棵树上建立虚树，在第二棵虚树上枚举 LCA，然后大概是在第三棵树上找到 $v$ 子树内点集合的直径端点，跟 $u$ 前面做完的子树的直径端点合并。

对虚树归并排序，$\Theta(n \log n)$。

现在已经变成套路题了。

不难发现我们本质上是求经过点 $u$ 的 $s_i,\,t_i$ 构成的链并，经典结论，以 dfn 为下标，树上差分线段树合并维护链并大小即可。

$\Theta(n \log n)$。

欧拉序动态直径板子。

具体来说我们发现 $[e_l,\,e_r]$ 中间的深度最小值就是它们的 LCA，维护两边深度最大值减去 $2 \times$ 深度最小值的最大值即可，这是线段树可维护的。

改边权是区间加，这是容易的。

$\Theta(n \log n)$。

处理出 $t_i$ 代表 $i$ 边删除的时刻，我们需要求出一个最小的 $t_i$ 尽可能大的路径，排序 $t$ 后是比较字典序，其它边都可以被删，这个路径删不了。主席树做比较字典序即可。$\Theta(n \log^2 n)$。

基于这个有个贪心做法，$\Theta(n \log n)$。

正常做法就是纯种大份题，不想做（建议学 A_zjzj 做法orz） 。

离线下来扫描线，倍增值域分块套 fhq 即可。

平衡树有交合并是什么做法。

$\Theta(n \log^2 n)$。

Check 一条路径是简单 Xor Hashing，然后放到点分树上，以子树为信息维护最小最大值及出现次数 Check $[l,\,r]$ 是不是在两个以下的子树内，然后就能找到对应子树，对每个子树维护平衡树查询 $[l,\,r]$ 内离根最远的点即可。

$\Theta(n \log^2 n)$。

大概率做复杂了吧。

两条路径有交，当且仅当一条路径的 LCA 在另一条路径上。

离线下来把路径挂到 LCA 上，考虑枚举深度小的那个 LCA，考虑 dsu on tree，先枚举另一个 LCA 在轻子树内的情况，这可以直接暴力，做完后递归，另一个 LCA 在重子树内是简单二维数点。

$\Theta(n \log^2 n)$。

塞了一堆 NOIP 原题，不放了。

令 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)$。

某次正睿的 T1。

首先 $n = 1$ 先手当然必胜。

考虑 $n = 2$，不难发现谁合并谁输，所以都不会合并。双方最后会拖到剩下两个 $1$ 的情况，这是 $a_i - 1$ 的 nim。

然后 $n = 3$，我们无论如何都有方法使得剩下的两个数异或和为 $0$。

然后可以猜测奇数区间必胜，偶数 $a_i - 1$ nim。

那么可以莫队维护，$\Theta(n \sqrt n)$。

很严谨的证明似乎没那么容易。

分开山峰和山谷，当只考虑山谷的时候，先计算一个数必须的代价。计算完后，当一个数从右边移动到左边，那么其代价是固定的（它为右端点的逆序对数），我们记录这个代价，加入一个数的时候是后缀减，取出全局为 $0$ 的数放到左边。

$\Theta(n \log n)$。