线段树优化建图

有一类经典的问题,之前见过很多次了,好像某一场区域赛的热身赛里就出过:一维数轴上有n个炸弹,\(x_i,r_i\)分别表示第i个炸弹的位置和引爆半径,即如果引爆炸弹i,那么位置在\([x_i-r_i,x_i+r_i]\)范围内的炸弹都会爆炸,并且引发连锁反应。然后比如询问最少引爆几个炸弹才能全部炸完。

首先一个建图思路是如果i能引爆j,那么i向j连一条边,做tarjan求强连通分量就可以知道很多信息了。但是这样暴力连边是\(O(n^2)\)的,需要优化。一个显然的观察是,一个点i的引爆范围是一段区间(这句是废话),所以是和一个区间的点连边,那么我们把炸弹按位置排序后,1到n编好号,建线段树,线段树每个点向左右儿子分别连边。如果i要向区间(l,r)所有点连边的话,就在线段树中将区间(l,r)分解成\(O(logn)\)条线段,这样就转化成了向对应的线段树中的一些点连边,总的边数就是\(O(nlogn)\)。

来看两道具体的题目:

bzoj 5017 [Snoi2017]炸弹

询问如果把第 i 个炸弹引爆,将引爆多少个炸弹。

线段树优化建图,然后tarjan,答案是从i所在的SCC出发,能走到的SCC含有的原炸弹数之和。因为对于每个i都要询问,所以这里不能暴力,一个方法是在这个DAG的反图上拓扑序dp一下。

 

Petrozavodsk Winter-2018. Carnegie Mellon U Contest A Mines

现在每个炸弹多了一个初始的引爆费用,因为连锁发生的爆炸是免费的。有q次修改,每次修改一个炸弹的费用,对于每次修改都要查询当前要引爆所有炸弹的最小花费。

前面的操作都一样,首先一个显然的想法是只要引爆DAG中所有入度为0的SCC里的费用最小的炸弹。然后有个致命的问题是,入度为0的SCC可能不含有原1到n号点,所以需要做拓扑排序删掉没用的点,之后对于每次询问用set维护即可。