c++ - 我们如何在给定的子矩阵中找到不同元素的数量？

Question

给定一个 N*N 矩阵和 Q 查询相同的给定矩阵。每个查询的形式为 x1,y1,x2,y2。我们必须找到由 (x1,y1) 和 (x2,y2) 分别定义为左上角和右下角的子矩阵中不同元素的数量。约束：N<=300 Q<=10^5 我正在使用简单的方法来迭代每个查询的子矩阵。有没有更好的方法？

Answer 1

这取决于您可以预期的查询数量以及可以预期的相同查询的数量。

一种方法是“记忆”查询，简单地存储每个查询和结果，并在进行更严肃的工作之前进行查找。

一种更针对问题的方法——可能是你的老师所追求的——是为每个 (right,bottom)=(x,y) 计算 (0, 0, x, y) 的不同元素。然后是简单的集合论来处理每个查询。但是进行原始计算非常耗时。

请记住添加对此 SO 答案的引用。