E - 2xN Grid

题意

给你一个 \(2\times L\) 的网格，但是 \(L\) 很大，所以用以下形式压缩：

将同一个颜色的连续段视为一个整体，那么每一行就可以用若干个二元组 \((a_i,b_i)\) 表示，其中 \(a_i\) 为颜色，\(b_i\) 为连续段的长度。保证长度 \(\le10^5\)。

输入以上述形式压缩，现在让你求出有多少个位置上下两个元素相同。

Solution

首先很容易就能算出连续段的左右端点，这样就转化为了对若干个区间的操作。

然后一个看起来很合理的做法就是，从左到右同时扫描两个数组，然后取交集计算即可。

实际上也是对的。双指针即可，时间复杂度 \(O(n)\)，可以通过此题。

注意要开 long long。

代码。

F - Sugar Water 2

比较奇怪的二分题。

首先把分子上的 \(100\) 拿掉，这样浓度就变成了糖质量和糖水质量的比值。

考虑二分这个浓度 \(x\)，因为糖和糖水的比值是 \(\dfrac{x}{1}\)，所以糖和水的比值就是 \(\dfrac{x}{1-x}\)

其中 \(x\) 是糖的质量，\(y\) 是水的质量。

考虑实现 check 函数：由于要求当前浓度 \(mid\) 是第 \(k\) 大，所以只需要算出 \(n\times m\) 中方案中有多少种是 \(\ge mid\) 的即可。如果 \(<k\)，说明浓度大了，令 \(r=mid\)；否则，说明浓度小了，令 \(l=mid\)。

所以现在的问题就转化为了，如何求出有多少种方案的浓度 \(\ge\) 一个数 \(x\)。

假设糖质量为 \(a\)，水质量为 \(b\)，那么可以根据上面计算的糖和水的比算出 \(s=a-\dfrac{x}{1-x}b\)。而 \(s\) 的含义就是“当前糖的质量比凑出浓度为 \(x\) 的糖水所需要的糖的质量要多多少”。因此我们只需要从两个数组当中分别挑出一杯糖水，使得其 \(s\) 之和 \(\ge0\) 即可。

这个过程可以二分查找，这样就可以以 \(O(m\log n)\) 或者 \(O(n\log m)\) 的复杂度完成 check 了。再加上外层的二分，时间复杂度是 \(O(mk\log n)\) 的。其中 \(k\) 为外层二分次数，这里我设置为 \(100\)，足够满足精度限制，也可以理解为是 \(\log^2\) 的。

最后乘 \(100\) 即可。

再就是 \(n\times m\) 会爆 int，要开 long long。

代码。

G - Distance Queries on a Tree

树剖板子。

由于树剖不是很容易处理边权，因此考虑一个经典套路：由于一个节点只有一个父亲，因此我们只需要把边权赋在儿子节点上，就可以唯一地代表儿子 \(\to\) 父亲这条路径的权值。

实际操作只需要判断深度即可，然后剩下的就是正常的树剖操作了。注意 \(lca\) 的点权是 \(lca\to fa(lca)\) 这条边的边权，不在 \(x\to y\) 的路径上，单独排除这个点即可。

然后就做完了，时间复杂度 \(O(m\log^2n)\)，可以通过此题。

当然这道题也可以维护节点到根节点路径的权值和。这样每次修改相当于对儿子节点子树内的所有点的点权进行修改，DFS 序搞一下即可。查询差分一下即可，时间复杂度 \(O(m\log n)\)，更为优秀。

树剖。

更好的做法。