题目链接 题意: 求矩形周长并. 思路: 线段树+扫描线. 和前面的求面积并比较类似,我们先考虑平行x轴的线段,考虑线段树,维护的一段区间中被矩形覆盖的次数cnt和至少覆盖一次的长度的len. 只不过我们这次求的是每条扫描线的长度对周长的贡献,因此不需要乘高度. 需要注意的是,每条扫描线对周长的贡献,是目前扫描线的长度,与上一次扫描线长度的差的绝对值.(不是与上一次答案的差的绝对值!) 演示x轴求长度和的部分 图片来自 lwt聚聚的博客 以及一个小细节是,求面积的时候,最后一条扫描线对答案是没有贡献的(因为每次是求当前扫描线与下一条扫描线之间的面积) 但是求周长的时候,最后一条扫描线是一定会对答案有贡献的. /* ...