在大矩陣中切換和計算查詢

Question

給定10^18×10^18的矩陣。每個單元格都是0或1.最初都是0.

現在我們需要執行Q查詢。我們有兩種類型的查詢：

1×L R：如果x = 0，那麼就意味着我們要切換行1,1 + 1，...，R的所有單元格的值。 否則(x = 1)我們應該對列號l，l + 1，... r進行此操作。我們需要在該矩陣的子矩形中打印標記爲1的單元格的數量，該矩形由行數l，l + 1，...，r和列數x，x + 1組成， ...，y。

現在，如果矩陣的大小很小，這可能已經完成。但如何爲10^18大小的矩陣做到這一點？我們不能創建矩陣，我們需要一些算法來有效地存儲這些值以回答所有查詢。

查詢數可能高達100 000.我怎樣纔能有效地做到這一點？

Answer 1

對於每個單元格，您都可以通過了解其列已被切換的次數以及其行已被切換的次數來計算其值。其實你只需要知道這兩者的總和是偶數還是奇數，並且因此足以知道他們每個人是單獨的還是偶數的。這還不夠，2E18位仍然太多了，但我們可以使用間隔樹 - 查詢的性質使其非常適合，並且每個元素可以輕鬆地顯示爲「存在/不存在」。

因此，要保留兩個間隔樹，一個用於跟蹤哪些行被切換爲奇數次，另一個用於跟蹤哪些列已被切換奇數次。

第二個查詢有點棘手，在某種程度上它類似於兩個間隔樹的乘法，產生了一個「矩形樹」，但是你不需要明確地構建它。假設樹已經被限制在查詢範圍內（可以隱式執行）。對於一棵樹中的每個當前範圍和每個不存在的範圍在其他樹中添加它們製作的矩形區域的總數爲1。然後用交換的樹做同樣的事情。

這是一個可視化，黑色範圍表示間隔樹的內容，紅色矩形表示矩陣的隱含內容。上面的算法訪問每個紅色矩形並添加區域。