给定一个 N*N 矩阵，并对同一给定矩阵进行 Q 次查询。每个查询的形式为 x1,y1,x2,y2。我们必须找到分别由 (x1,y1) 和 (x2,y2) 定义为左上角和右下角的子矩阵中不同元素的数量。 约束:N<=300 Q<=10^5 我使用简单的方法迭代每个查询的子矩阵。有没有更好的方法？
最佳答案
这取决于您可以预期的查询数量，以及您可以预期的相同查询的数量。
一种方法是“内存”查询，简单地存储每个查询和结果，并在进行更认真的工作之前进行查找。
一种更针对特定问题的方法(可能是您的老师所追求的)是为每个 (right,bottom)=(x,y) 计算 (0, 0, x, y) 的不同元素。然后用简单的集合论来处理每个查询。但进行原始计算非常耗时。
请记住添加对此答案的引用。
关于c++ - 我们如何找到给定子矩阵中不同元素的数量？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20487406/