本文共 591 字，大约阅读时间需要 1 分钟。

在解决这个问题时，我最初尝试使用暴力枚举每个点的竖着和横着的两个点，但发现这种方法需要三重循环，显然会超时。因此，我意识到这应该是一个动态规划问题，特别是涉及二维前缀和的类型。

我决定定义两个前缀和数组：a和b。其中，a[i][j]表示从左边到i行，到j列为止，横着有连续的两个点的情况的总数；b[i][j]表示从上边到i行，到j列为止，竖着有连续的两个点的情况的总数。

通过分析，我得出以下递推关系：

• a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1]
• b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1]

接下来，我处理每个查询时，使用这些前缀和数组来快速计算符合条件的数量。

对于每个查询矩形(x1, y1, x2, y2)，符合条件的横着的连续两个点的数量可以通过a数组查询得到：sum += a[x2][y2] - a[x1][y2] - a[x2][y1-1] + a[x1][y1-1]

同样，竖着的连续两个点的数量通过b数组查询：sum += b[x2][y2] - b[x1-1][y2] - b[x2][y1] + b[x1-1][y1]

最终的答案是这两个数量的总和。

通过这种方法，预处理后的前缀和数组使得每个查询的响应时间大大减少，避免了暴力枚举的高时间复杂度，成功解决了问题。

转载地址：http://ztwzz.baihongyu.com/