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

· · 题解

:::info[题意]{open}

给你 n 个点（跳跃球），kid 能从第 i 个点跳跃到第 j 个点当且仅当 y_i + d \geqslant |x_i-x_j| + y_j（d 是给定常数），求 kid 从第 c 个点出发最多能经过多少个点（跳跃球）。n\leqslant 10^5，d,x_i,y_i \leqslant 10^8。

:::

首先不难发现正城弱化版（n\leqslant 3000）其实就是 P3387 【模板】缩点的双倍（n 倍？）经验，直接按题意（转化出上面的有边条件）\mathcal O(n^2) 暴力建图就行。缩点之后记每个 scc 含 a_i 个跳跃球，那么设 dp_u 表示由点（scc）u 出发最多经过的跳跃球数，方程就是 dp_u = a_u + \max\limits_{u\to v}dp_v，发现转移是逆拓扑序的，所以可以直接省掉建新图和拓扑排序的过程（详见《一个略去拓扑排序的 dp 方式。》）。

来到逆城，考虑优化。tarjan 求 scc 这一块应该是动不了了，于是考虑优化建图。最最常见的就是线段树优化建图，直接套就可以把 P5025 秒了，但该题的坐标系是二维的啊，所以不能直接套。

对着上面那个有边条件使劲瞪，发现第 i 个点会和它往上平移 d 个单位后的点的下方（伞状范围）所有点连边。发现这样有点难受，考虑旋转坐标系（感性理解，推柿子证明见下），旋转后就是形如 x'_i+d\geqslant x'_j,\ y'_i+d\geqslant y'_j，即这个点向右向上分别平移 d 后左下方所有点。

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' 一维进行扫描线，需要处理两种操作：在线段树上更新（纵坐标（y'）特定位置添加了一个点），以及处理查询（这个点往当时的纵坐标的一个区间内所有点连边），但是你更新的时候不能影响到之前查询建的边，于是考虑像主席树一样更新，从线段树根节点一路下来新建一条链然后建边，查询就直接查询区间就好啦。不过警示后人，最后新建的叶子节点还需要向原叶子节点连边！（目的请自行体会。）

建完图就可以美美套 tarjan 缩点模板通过啦。具体实现细节可参考 AC Code，时间遥遥领先。时空复杂度均为 \mathcal O(n\log W)，其中 W 为坐标值域。

（当时在餐桌上想了 1h，其实想到的是另一个使用链表+线段树来优化建图的玩意，可是回家发现这东西和主席树好像没啥区别，于是此题加强版也成了板子，就没有真正放到 R2 去 qwq）

最后来几道练习题：

Thanks for watching!