You are given two 0-indexed arrays nums1 and nums2 and a 2D array queries of queries. There are three types of queries:
For a query of type 1, queries[i] = [1, l, r]. Flip the values from 0 to 1 and from 1 to 0 in nums1 from index l to index r. Both l and r are 0-indexed.
For a query of type 2, queries[i] = [2, p, 0]. For every index 0 <= i < n, set nums2[i] = nums2[i] + nums1[i] * p.
For a query of type 3, queries[i] = [3, 0, 0]. Find the sum of the elements in nums2.
Return an array containing all the answers to the third type queries.
Example 1:
Input: nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]
Output: [3]
Explanation: After the first query nums1 becomes [1,1,1]. After the second query, nums2 becomes [1,1,1], so the answer to the third query is 3. Thus, [3] is returned.
Example 2:
Input: nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]
Output: [5]
Explanation: After the first query, nums2 remains [5], so the answer to the second query is 5. Thus, [5] is returned.
Constraints:
1 <= nums1.length,nums2.length <= 105
nums1.length = nums2.length
1 <= queries.length <= 105
queries[i].length = 3
0 <= l <= r <= nums1.length - 1
0 <= p <= 106
0 <= nums1[i] <= 1
0 <= nums2[i] <= 109
Solutions
Solution 1: Segment Tree
According to the problem description:
Operation $1$ is to reverse all numbers in the index range $[l,..r]$ of array nums1, that is, change $0$ to $1$ and $1$ to $0$.
Operation $3$ is to sum all numbers in array nums2.
Operation $2$ is to add the sum of all numbers in array nums2 with $p$ times the sum of all numbers in array nums1, that is, $sum(nums2) = sum(nums2) + p * sum(nums1)$.
Therefore, we actually only need to maintain the segment sum of array nums1, which can be implemented through a segment tree.
We define each node of the segment tree as Node, each node contains the following attributes:
l: The left endpoint of the node, the index starts from $1$.
r: The right endpoint of the node, the index starts from $1$.
s: The segment sum of the node.
lazy: The lazy tag of the node.
The segment tree mainly has the following operations:
build(u, l, r): Build the segment tree.
pushdown(u): Propagate the lazy tag.
pushup(u): Update the information of the parent node with the information of the child nodes.
modify(u, l, r): Modify the segment sum. In this problem, it is to reverse each number in the segment, so the segment sum $s = r - l + 1 - s$.
query(u, l, r): Query the segment sum.
First, calculate the sum of all numbers in array nums2, denoted as $s$.
When executing operation $1$, we only need to call modify(1, l + 1, r + 1).
When executing operation $2$, we update $s = s + p \times query(1, 1, n)$.
When executing operation $3$, we just need to add $s$ to the answer array.
The time complexity is $O(n + m \times \log n)$, and the space complexity is $O(n)$. Where $n$ and $m$ are the lengths of arrays nums1 and queries respectively.