扫描线扫描线是重要的思想，能解决的问题诸如：区间覆盖点数，区间询问（一般不可修改），侧重考虑构思：加点，解决左端点。 典例典例一：模板扫描线其实只要维护一个区间覆盖点数，再上左右扫一次，上下扫一次。 典例二：P8037 [COCI2015-2016#7]Prokletnik重心在定右端点后考虑能扩展最左的左端点，搞完用树装数组维护后缀 $max$...

树链剖分树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作“实链剖分”），大多数情况下（没有特别说明时），“树链剖分”都指“重链剖分”。引自：OI-WIKI 重链剖分我们给出一些定义 定义 重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。...