下文 \(n=1 \times 10^5\)。

T1: \(O(n^2)\) 100pts

T2: Unknown

T3: \(O(n^2)\) 100pts

T4: \(O(n^2\log n)\) 100pts

總結：。。。

T1 典中典中點

T2 拆點最短路

T3 鬼街

T4 李超線段樹合并模板題 Escape Through The Leaf