专栏文章

题解：「NAPC #1」rStage3 ~ Hard Jump Refreshers

yy_kx_b
P9431题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio1iudj
此快照首次捕获于
2025/12/02 11:50
3 个月前
此快照最后确认于
2025/12/02 11:50
3 个月前
查看原文
问 kid 最多能跳到多少个跳跃球也是计数题（确信）
题意
给你 nn 个点（跳跃球），kid 能从第 ii 个点跳跃到第 jj 个点当且仅当 yi+d⩾∣xi−xj∣+yjy_i + d \geqslant |x_i-x_j| + y_j（dd 是给定常数），求 kid 从第 cc 个点出发最多能经过多少个点（跳跃球）。rs3 中 n⩽105n\leqslant 10^5（在原题中提交，单个点时限 50ms？）。
首先不难发现正城弱化版（n⩽3000n\leqslant 3000）其实就是 P3387 【模板】缩点 的双倍经验，直接按题意 O(n2)\mathcal O(n^2) 暴力建图就行，具体转化可以参考本题其他题解（其实上面简要题意已经摆出来了）。
考虑优化。tarjan 求 scc 这一块应该是动不了了，于是考虑优化建图。最最常见的就是线段树优化建图，直接套就可以把 P5025 秒了，但该题的坐标系是二维的啊，所以不能直接套。
对着上面那个有边条件使劲瞪，发现第 ii 个点会和它往上平移 dd 个单位后的点的下方（伞状范围）所有点连边。发现这样有点难受，考虑旋转坐标系（感性理解，推柿子证明见下），旋转后就是形如 xi′+d⩾xj′, yi′+d⩾yj′x'_i+d\geqslant x'_j,\ y'_i+d\geqslant y'_j，即这个点向右向上分别平移 dd 后左下方所有点。
yi+d⩾∣xi−xj∣+yj⇒{yi+d⩾xi−xj+yj⇒(yi−xi)+d⩾(yj−xj)yi+d⩾−xi+xj+yj⇒(yi+xi)+d⩾(yj+xj)i.e. xi′+d⩾xj′, yi′+d⩾yj′.y_i + d \geqslant |x_i-x_j| + y_j\Rightarrow\\ \begin{cases}y_i+d\geqslant x_i-x_j+y_j\Rightarrow(y_i-x_i)+d\geqslant (y_j-x_j)\\ y_i+d\geqslant -x_i+x_j+y_j\Rightarrow (y_i+x_i)+d\geqslant(y_j+x_j)\end{cases}\\ \text{i.e. }x'_i+d\geqslant x'_j,\ y'_i+d\geqslant y'_j.
发现这个东西长得有点像二维偏序/二维数点！（但是，BIT 优化建图，有点抽象吧（好像确实可以，没试过），于是考虑把之前的线段树请回来。）考虑对 x′x' 一维进行扫描线，需要处理两种操作：在线段树上更新（纵坐标（y′y'）特定位置添加了一个点），以及处理查询（这个点往当时的纵坐标的一个区间内所有点连边），但是你更新的时候不能影响到之前查询建的边，于是考虑像主席树一样更新，从线段树根节点一路下来新建一条链然后建边，查询就直接查询区间就好啦。不过警示后人，最后新建的叶子节点还需要向原叶子节点连边！（目的请自行体会。）
建完图就可以美美套 tarjan 缩点模板通过啦。具体实现细节可参考 AC Code，时间遥遥领先。时空复杂度均为 O(nlog⁡V)\mathcal O(n\log V)，其中 VV 为坐标值域；也许可以通过离散化达到 O(nlog⁡n)\mathcal O(n\log n)，但是主席树已经动态开点了，何必再写离散化呢。
（当时在餐桌上想了 1h，其实想到的是另一个使用链表+线段树来优化建图的玩意，可是回家发现这东西和主席树好像没啥区别，于是此题加强版也成了板子，就没有真正放到 R2 去 qwq）
最后来几道练习题：
Thanks for watching!

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...