说实话,这个其实也没什么。线段树优化建图就是一个简单的技巧而已。
假设有 $n$ 个点,每个点都要向其他的很多点($\Theta(n)$)连边,那么建图的时间复杂度就是 $\Theta(n^2)$ 的。
但是利用一点点特殊性质,就可以优化到 $\Theta(n\log_2n)$。
举个例子:每个点向连续的 $K$ 个点连边。
把 $K$ 个点看作线段树最底下的那些长度为一的区间,其他的区间看作是虚点(一些为了快速加边的特殊点,有点像正常线段树的 lazytag
),然后画画图,就好了。
显然最多可以连接 $\Theta(\log_2K)$ 条边,所以时间复杂度是 $\Theta(n\log_2K)$。
推荐题目:
POI2015 PUS
I’m not sure exactly why but this website is loading extremely slow for me.
Is anyone else having this problem or is it a issue on my end?
I’ll check back later and see if the problem still exists.