Untitled
6.13 题解
D - Glass Carving
Des
有一个 $w\times h$ 的玻璃每一次可以在 横/竖 方向上某一个位置切一刀，求最后的最大的矩形面积。
Sol
首先，一个显而易见的结论是，对于横方向和纵方向，我们都取最大值，于是答案就是它们的乘积。
考虑如何维护横方向和纵方向的最大值。
因为切刀是在 $(x,x+1)$ 的中间切的，这很不好，因此我们把矩形变成 $(2w-1)\times(2h-1)$ 大小，其中对于 $\forall i \in [1,n)$，第 $2i$ 个位置表示原来 $(i,i+1)$ 的 缝隙。这样，我们在修改的时候就可以精确地找到它的位置。
于是我们使用两只线段树，分别统计横向和纵向的切割情况。初始线段树都设成 $1$，对于一次修改 $x$，我们把 $2x$ 这个地方修改成 $-\infty$，于是最长的长度就是整只线段树的最大子段和。记 $ans$ 是最大子段和，那么它还原回去的最大长度就是 $\frac{ans+1}{2}$。
当然，你也可以发明一个最长连续 $1$ 的个数，这个东西和最大子段和很像，也不是太难写 （我就是这么写的$QwQ$）
E - 树
Des
给定一棵树，支持两种操作：
- 标记一个点 $x$。
- 查询一个点 $x$ 的祖先中，距离 $x$ 最近的被标记的点是哪个。
其中 $1$ 是根，并且最开始就被标记了。
Sol
这里提供一个很臭的 $n\log^3 n$ 做法。（但是是三个常数很小的 $\log$，因此可以过去。）
首先，如果我们打标记就相当于给节点的权值 $+1$，那么问题就变成了找到 深度最小的节点使得它到 $x$ 之间没有节点被打标记，然后输出这个节点的父亲。然后，我们发现，在 $1-x$ 不断向下查找的过程之中，$1-u$ 的标记的点的数量显然是单调不增的。也就是说，如果 $x-u$ 之间存在打标记的点，那么对于 $f = fa_u$，显然有 $x-f$ 之间有打标记的点。于是，我们就想到了用倍增来解决这个问题。我们从大到小不断改变二的次幂，凑出一个长度使得 $x-u$ 之间不存在打标记的点。输出 $fa_u$ 即可。
然后修改就是树上单点修，查询就是树上路径查询，直接剖即可。
复杂度 $O(n\log ^3 n)$，其中剖和树状数组常数都很小，而倍增是稳定的一个 $\log$。
F - 魔法树
剖的板子，不讲了。
G - 二进制方程
Des
有方程形如：
$$\overline{x_1x_2\dots x_n} = \overline{y_1y_2\dots y_n}$$
其中 $x$ 或 $y$ 的某一些区间会被未知数替代，比如说 $x$ 中的区间 $[3,5]$ 可能会变成 $a$，那么 $a$ 就代表三位二进制数 $\overline{pqr}$。
若给定一共有多少个未知数、每个未知数占据多少位，求可能的等式的数量。
Sol
我们把两个二进制数拆开来写：
如果，我们有 $x[3,5] = y[1,3] = a$，$x[1,2]=y[6,7]=b$，则有如下网络关系：
也就是有联通块关系如下：
有两种联通块，也就是有两种不同的选择，于是答案就是 $2^2$。
但是我们没有考虑方程中 $0$ 和 $1$ 的情况。也就是说，如果某一个位置，比如 $y_2=1$，那么总有 $2,4,7$ 这三个地方都是 $1$，也就是说，它们不能自由选择了。于是这里的答案应该是 $2^1=2$。
因此，我们把 $k$ 个变量展开来，再把 $X$ 和 $Y$ 展开来。设 $i$ 个变量的长度为 $len_i$，我们给 $0,1$ 分配一个位置，给变量 $i$ 分配 $len_i$ 个位置并分别标号。对于 $X$ 和 $Y$ 中的一个位置 $X_i$ 和 $Y_i$，总能对应带我们给出的类似于内存条的东西上的一个位置上，我们把这个东西记录下来，然后在并查集上合并 $X_i$ 和 $Y_i$，最后二的联通块个数次幂就是答案。
值得注意的是，对于 $0$ 和 $1$ 在一个联通块的情况，总需要输出 $0$。
H - 运输计划
Des
给定一棵树，在树上有 $m$ 条路径，其中每一条路径形如 $(u,v)$。要求将其中的一条边 $x\to y$ 边权改成 $0$，使得最小化
$$\max_{i=1}^m dis(u_i,v_i)$$
Sol
首先，一个显而易见的结论是，改变的那条边一定在最长的路径之上，否则，答案一定是那条最长的路径。
于是我们考虑枚举最长路径上的每一条边。对于一条边 $(u,v,w)$，显然，如果将 $w\leftarrow 0$，则所有的路径可以分为两种。一种是经过边 $(u,v,w)$ 的路径；另一种是不经过边 $(u,v,w)$。其中，经过该边的路径显然都需要把最终的答案减去 $w$，而最长的路径又一定经过该边，因此经过该边的路径的长度最大值就是最长的路径长度减去 $w$。
然后我们再来讨论没有经过该边的路径。
首先，我们考虑能不能在线求出，但是显然我们并不能够在能够接受的复杂度之内算出不经过该边的路径有哪些，那我们不妨提前都预处理出来。
对于一条路径 $(u,v,t)$，其中 $t = dis(u,v)$，它不经过的边在计算不经过该边的最大路径长度的时候都会把它计算到，因此我们把这些路径跟 $t$ 取一个 $\max$，这样，在处理完所有路径的时候，每条边的 $\max$ 就是不经过该边的最长路径长度。接下来我们考虑如何快速在一条路径之外取 $\max$。由树剖，我们知道，树上的一条路径可以唯一分解成最多 $\log n$ 条 $dfn$ 连续的链，因此，我们把这些连续的 $dfn$ 段记录下来，然后按照左端点排序，这样我们就得到了一堆按照先后排序的没有交的区间。我们把这些区间在 $[1,n]$ 的全集意义下取反集，就可以知道那些边是会被修改的。
有的同学会问，我们怎么统计边的信息呢？这就用到了一个方法，把边权放到点上统计。具体地，对于外向边 $x\to y$，我们可以把权值 $z$ 统计到 $y$ 上。也就是说，如果有边 $x\to fa_x$，我们把这条边的信息统计到 $x$ 而不是 $fa_x$ 上。特别地，$1$ 号节点不统计任何信息。
这样，我们就完成了这道题。