给定一个 10^18 × 10^18 的矩阵。每个单元格要么是 0 要么是 1。最初都是 0。
现在我们需要执行 Q 查询。我们有两种类型的查询:
1 x l r:如果x = 0，则意味着我们应该切换第 l、l+1、...、r 行中所有单元格的值.
否则 (x = 1) 我们应该对第 l、l+1、... r 列执行此操作。
2 l r x y:我们需要打印这个矩阵的子矩形中标记为 1 的单元格的数量，由行号 l、l+1、...、r 和列号 x 组成， x+1, ..., y。
现在如果矩阵的尺寸很小，这可以做到。但是如何为 10^18 大小的矩阵执行此操作？我们无法创建矩阵，我们需要一些算法以有效的方式存储这些值以回答所有查询。
查询数最多可达 100 000。我怎样才能有效地做到这一点？
最佳答案
对于每个单元格，您可以通过了解其列被切换的次数和其行被切换的次数来计算其值。实际上你只需要知道这两者的和是偶数还是奇数，为此知道它们中的每一个单独是偶数还是奇数就足够了。这还不够，2E18 位仍然太多，但我们可以使用区间树 - 查询的性质使其非常适合，并且每个元素 1 位可以很容易地表示为“存在/不存在”。
因此保留两棵间隔树，一棵跟踪哪些行被切换了奇数次，另一棵跟踪哪些列被切换了奇数次。
第二个查询有点棘手，在某种程度上它类似于两个区间树的乘法，产生“矩形树”，但您永远不必显式构建它。假装树已经限制在查询范围内(您可以隐式执行此操作)。对于一棵树中的每个存在范围和另一棵树中的每个不存在 范围，将它们构成的矩形的面积添加到 1 的总数。然后对交换的树做同样的事情。
这是一个可视化，黑色范围代表区间树的内容，红色矩形代表矩阵的隐含内容。上面的算法访问每个红色矩形并添加区域。
关于algorithm - 在大型矩阵中切换和计数查询，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32024884/