主題
題目連結：
題目意譯：
你被給定兩個索引值從 0 開始的陣列 nums1 和 nums2 以及一個二維詢問陣列 queries。現在有三種詢問類型：
對於一筆類型 1 的詢問，queries[i] = [1, l, r]。將 nums1 索引值 l 到 r 的部分中的 0 變成 1 、 1 變成 0。l 和 r 都是從 0 開始數的索引值。
對於一筆類型 2 的詢問，queries[i] = [2, p, 0]。對於每個索引值 0 ≦ i < n，將 nums2[i] 之值設為 nums2[i] + nums1[i] × p。
對於一筆類型 3 的詢問，queries[i] = [3, 0, 0]。計算出 nums2 中元素總和。
回傳一個陣列，其包含著所有類型 3 的詢問之答案。
限制：
1 ≦ nums1.length,nums2.length ≦ 10 ^ 5
nums1.length = nums2.length
1 ≦ queries.length ≦ 10 ^ 5
queries[i].length = 3
0 ≦ l ≦ r ≦ nums1.length - 1
0 ≦ p ≦ 10 ^ 6
0 ≦ nums1[i] ≦ 1
0 ≦ nums2[i] ≦ 10 ^ 9
範例測資：
範例 1：
輸入： nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]
輸出： [3]
解釋： 在第一筆詢問後，nums1 變成 [1,1,1]。在第二筆詢問後，nums2 變成 [1,1,1]，所以第三筆詢問的答案為 3。因此回傳 [3]。
範例 2：
輸入： nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]
輸出： [5]
解釋： 在第一筆詢問後，nums2 維持為 [5]，所以第二筆詢問的答案為 5。因此回傳 [5]。
解題思維：
首先我們可以看到類型 2 的詢問實際上對於類型 3 的詢問來說，等價於把詢問前 nums2 的元素總和多加上現在 nums1 的總和乘以 p 之值。
而多次的類型 2 代表著最一開始 nums2 總和不動，每次都只加上「當前」的 nums1 總和乘以該次詢問的 p 值便可以得到所求（如果有類型 3 的詢問的話）。
所以實際上我們只需要去進行 nums1 的區間修改並維護整體的總和。而這個可以使用線段樹（Segment Tree）來維護，參見這題的介紹。不過現在我們是要為每筆詢問修改某個區間。
因此如果每次詢問都是要翻轉整個 nums1，並且如果我們直接為每個節點重新計算數值，則實質上每次詢問我們等同於重建了線段樹。可以看到這樣並不理想，因為最糟時間複雜度為單次 O(n × log(n))，其中 n 為 nums1 的元素個數。
不過我們可以使用一種稱為懶人標記（Lazy Propagation）的方式來修改區間。核心思想就是不要「做到底」，也就是說如果現在看到的這個節點（注意每個節點代表著一段區間）完整地被包含於要修改的區間之中，則將其標記起來，「先」不用繼續往下做。
可以看到每一次修改的時候我們最多會把一個要修改的區間切成 O(log(n)) 塊。而如果把這些停留並做標記的節點視為「葉節點」，則「本次詢問的樹」看到的節點數也是 O(log(n)) 個。因此單次時間複雜度為 O(log(n))。
而第一次修改時樹上沒有任何標記，固然沒有問題。那麼接下來的修改遇到有標記的節點該怎麼辦呢？如果現在看到的有標記的節點是整棵線段樹的葉節點，則就直接再次修改數值即可；如果是內部節點，則把左右兩個子樹的根節點標記起來。
注意到對於本題來說，由於有標記代表著之前把「最原本」的 nums1 此區間的數值「翻轉」，而如果再次被標記則代表著翻轉後再翻轉一次，即等於沒有翻轉。所以很自然地可以順便「消掉」標記。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
