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