【bzoj5017】[Snoi2017]炸弹 线段树优化建图+Tarjan+拓扑排序
题目描述在一条直线上有N个炸弹，每个炸弹的坐标是Xi，爆炸半径是Ri，当一个炸弹爆炸时，如果另一个炸弹所在位置Xj满足： Xi−Ri≤Xj≤Xi+Ri,那么，该炸弹也会被引爆。 现在，请你帮忙计算一下，先把第i个炸弹引爆，将引爆多少个炸弹呢？ 输入第一行，一个数字N，表示炸弹个数。 第2∼N+1行，...
[POI2015][bzoj4383] Pustynia [线段树优化建图+拓扑排序]
题面bzoj权限题传送门luogu传送门思路首先，这个题目显然可以从所有小的点往大的连边，然后如果没环就一定可行，从起点（入读为0）开始构造就好了但是问题来了，如果每个都连的话，本题中边数是$O(n^2)$级别的，显然会挂发现两条性质：1.所有的限制条件中，给定的总点数不超过3e5个2.是一个点比一...