2024.10.23 李赛

definieren / 2024-11-17 / 原文

A.Close Group

直接状压。

B.P1054 [NOIP2005 提高组] 等价表达式

傻逼吗？？？？？？？怎么又不匹配的括号题面里还不说的？？？？？

建括号树，然后随一万个数判定即可。

C.P7217 [JOISC2020] 収穫

赛时感觉不可做就没做，看来我直觉还是挺准的，但是策队秒了。

最重要的一步是观察到每个人摘了苹果之后下一个摘苹果的人是固定的，这个虽然比较显然但是我感觉比较难注意到。

对于一个人 $i$，如果他摘完苹果之后下一个摘的人是 $j$，那么我们就连一条 $i \rightarrow j$ 的边，边权是中间间隔的时间。

不难发现形成了一棵内向基环树。

此时对于一个苹果树，能贡献到的人就是从第一个摘到它的人开始不断地跳出边，花费的时间就是第一个摘到它的人花费的时间与边权之和。

对于不在环上的询问，答案是子树内的能在规定时间内摘到它的苹果树的和。

具体来讲，对于一个第一个摘到它的人在这个点子树内的苹果树，记 $(u_0, t_0)$ 表示第一个摘到它的人和摘到的时间，那么要求就是：

\[\operatorname{Distance}(u, u_0) \le t - t_0 \]

通过深度表示距离并移项可得：

\[dep_{u_0} + t_0 \le dep_{u} - t \]

配合子树的限制形成了二维数点的形式，直接二维数点即可。

对于在环上的询问，先断环成链（环上的边向左指，不妨认为环上编号递增）。

记 $dis_u$ 表示点 $u$ 在断开的环上到环的一段的距离，$P$ 为环长。

对于一个苹果树，我们预处理出 $(u_0, t_0)$ 表示它第一次跳到环上是在 $t_0$ 时刻，跳到的点是 $u_0$。

考虑这个苹果树对一个询问 $(u, t)$ 的贡献：

\[\begin{cases} \max \left\{\left\lfloor \dfrac{(t + dep_u) - (t_0 + dep_{u_0})}{P} \right\rfloor + 1, 0 \right\},\text{ if }u \le u_0 ,\\ \max \left\{\left\lfloor \dfrac{(t + dep_u) - (t_0 + dep_{u_0})}{P} \right \rfloor, 0 \right\}, \text{ otherwise.} \end{cases} \]

发现两个形式是相似的，经过尝试后我们决定先考虑上面的一个。

记 $t + dep_u = q \cdot P + r, t_0 + dep_{u_0} = q_0 \cdot P + r_0$，则原式可化为：

\[\begin{aligned} &\left\lfloor \frac{(t + dep_u) - (t_0 + dep_{u_0})}{P} \right\rfloor + 1 \\ = \ & (q - q_0) + \left\lfloor \frac{r - r_0}{P} \right\rfloor + 1 \\ = \ & (q - q_0) + [r \ge r_0] \end{aligned} \]

发现当 $q - q_0 \ge 0$ 时，原式一定 $\ge 0$，否则一定 $\le 0$，所以我们只需钦定 $q \ge q_0$ 统计答案。

我们可以先通过排序双指针的方法求出 $q - q_0$ 的贡献，$[r \ge r_0]$ 的贡献可以二维数点。

考虑下面的式子，经过化简，可以发现就是

\[(q - q_0) + [r \ge r_0] - 1 \]

所以我们只需一起统计答案，最后把多算的贡献（大于 0 的部分）减掉即可。

剪掉的部分是：

\[\begin{cases} u > u_0 \\ t + dep_u \ge t_0 + dep_{u_0} \end{cases} \]

这个也是二维数点的形式。

时间复杂度 $O(n \log n)$。