海报

发布时间 2023-12-22 22:22:47作者: 最爱丁珰

这题目是扫描线另一经典应用:求矩形并的周长

我们对\(c\)数组的求法跟求面积的时候一样,考虑如何统计答案

我们考虑什么情况会对答案做出贡献

可以发现,我们可以将边分成垂直的边和水平的边,用相同的方法分别统计再相加,下面以求垂直的边为例

垂直的边对答案做出贡献的时候只会在某一次修改的时候

假设在这次修改前,我们\(c\)数组的和是\(x_1\),修改后\(c\)数组的和是\(x_2\),那么这个答案的贡献就是\(abs(x_1,x_2)\)

为什么?

如果这次修改是\(+1\),那么对于原来为\(0\)\(c\)数组的某个下标,他在这里就会出现一条长度为\(1\)黑线,我们就要把这个黑线统计成周长,对于原来不为\(0\)\(c\)数组的某个下标,这里不会出现黑线,也就不会统计

如果这次修改是\(-1\),那么对于原来为\(1\)\(c\)数组的某个下标,他在这里就会出现一条长度为\(1\)黑线,我们就要把这个黑线统计成周长,对于原来不为\(1\)\(c\)数组的某个下标,这里不会出现黑线,也就不会统计