P11453 [USACO24DEC] Deforestation S 题解

· · 题解

一道可以用差分约束做的题。

由于 l_i,r_i 很大，而树的个数仅有 3\times10^5 棵，首先可以将题目中的树的坐标和区间进行离散化处理。

于是树就可以有序映射到 [1,2\dots n] 的排列中。

可以对于前 i 个树中被砍掉的树的数量进行差分约束。

为了使跑差分约束时的数组名字统一，这里设前缀和数组为 dis。

由于在一个点上只有一颗树，可知前缀和数组 dis 有以下不等关系：

$dis_i - dis_{i-1}\leq1$ 和 $dis_{i-1}-dis_i\leq0

同时成立。

又根据题目中的至少保存的数目，可以知道

其中 $l$ , $r$ 为限制离散化中后的左右端点。 由于这里的边权都是非负的，所以可以用 dijkstra 算法。 时间复杂度：$O(T(n+m)\log n)$。 [代码](https://www.luogu.com.cn/paste/f2pvp9gb)