<p>You are given two <strong>0-indexed</strong> arrays <code>nums1</code> and <code>nums2</code> and a 2D array <code>queries</code> of queries. There are three types of queries:</p>

<ol>
	<li>For a query of type 1, <code>queries[i]&nbsp;= [1, l, r]</code>. Flip the values from <code>0</code> to <code>1</code> and from <code>1</code> to <code>0</code> in <code>nums1</code>&nbsp;from index <code>l</code> to index <code>r</code>. Both <code>l</code> and <code>r</code> are <strong>0-indexed</strong>.</li>
	<li>For a query of type 2, <code>queries[i]&nbsp;= [2, p, 0]</code>. For every index <code>0 &lt;= i &lt; n</code>, set&nbsp;<code>nums2[i] =&nbsp;nums2[i]&nbsp;+ nums1[i]&nbsp;* p</code>.</li>
	<li>For a query of type 3, <code>queries[i]&nbsp;= [3, 0, 0]</code>. Find the sum of the elements in <code>nums2</code>.</li>
</ol>

<p>Return <em>an array containing all the answers to the third type&nbsp;queries.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]
<strong>Output:</strong> [3]
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]
<strong>Output:</strong> [5]
<strong>Explanation:</strong> After the first query, nums2 remains [5], so the answer to the second query is 5. Thus, [5] is returned.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums1.length,nums2.length &lt;= 10<sup>5</sup></code></li>
	<li><code>nums1.length = nums2.length</code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code><font face="monospace">queries[i].length = 3</font></code></li>
	<li><code><font face="monospace">0 &lt;= l &lt;= r &lt;= nums1.length - 1</font></code></li>
	<li><code><font face="monospace">0 &lt;= p &lt;= 10<sup>6</sup></font></code></li>
	<li><code>0 &lt;= nums1[i] &lt;= 1</code></li>
	<li><code>0 &lt;= nums2[i] &lt;= 10<sup>9</sup></code></li>
</ul>

# This segment tree counts "ranges of 1's" (array indexes) and sums of
# ranges of 1's in parallel trees.
#
# The "sum" tree counts how many 1's were in the nodes below it if known,
# or just has 0 if unknown. The count will only be known if the node's
# children both have array indexes of a range of 1's.
#
# The "indexes" tree tracks array indexes of ranges of 1's. It tracks the
# start index (inclusive) and end index (exclusive), 1-indexed. It will be
# 0 if unknown.
class SegTree:

    def __init__(self, nums: List[int]):
        # Pad with a '0' we'll need for an end index if `nums` ends in 1
        nums = nums + [0]
        
        # Find 'n': Power of 2 needed to create leaf nodes
        self.n = 1 << (len(nums) - 1).bit_length()
        
        # Create two perfect binary trees: one for tracking the indexes
        # of ranges of 1's and another for tracking sums of ranges.
        self.idxs = [0] * (self.n*2)
        self.sums = [0] * (self.n*2)

        # Initialize leaf nodes for indexes of ranges of 1's
        # Ranges are denoted by the start (inclusive) and end (exclusive)
        # Ranges are 1-indexed to distinguish from zero
        prev = 0
        for i, num in enumerate(nums):
            if num ^ prev:
                self.idxs[self.n + i] = i + 1
                prev ^= 1

        # Update nodes above leaves by summing & merging ranges together.
        for i in range(self.n-1, 0, -1):
            self.update_node(i)
    
    def update_node(self, i: int):
        l, r = i*2, i*2+1
        l_is_idx = self.idxs[l] > 0
        r_is_idx = self.idxs[r] > 0
        if l_is_idx and r_is_idx:
            # Case A) We have both indexes of a range, so the diff between indexes is the
            # number of 1's in a row to sum up.
            self.sums[i] = self.idxs[r] - self.idxs[l]
            self.idxs[i] = 0
        elif not (l_is_idx or r_is_idx):
            # Case B) These are sums of 1's to sum up (no indexes)
            self.sums[i] = self.sums[l] + self.sums[r]
            self.idxs[i] = 0
        elif l_is_idx:
            # Case C) Left is an index, but we don't know what the right index is yet.
            # Handle by "shifting" left idx "up" by number of 1's summed on right side (if any).
            self.idxs[i] = self.idxs[l] + self.sums[r]
        else:
            # Case D) Right is an index, but we don't know what the left index is yet.
            # Handle by "shifting" right idx "down" by number of 1's summed on left side (if any).
            self.idxs[i] = self.idxs[r] - self.sums[l]
    
    def update(self, l: int, r: int):
        l_idx, r_idx = self.n + l, self.n + r
        
        # "Flip" range by toggling array indexes at L and R
        self.idxs[l_idx] = self.toggle_range_index(l)
        self.idxs[r_idx] = self.toggle_range_index(r)

        # Propagate changes up the trees
        self.propagate_changes(l_idx)
        self.propagate_changes(r_idx)
    
    def toggle_range_index(self, idx: int):
        if self.idxs[self.n + idx] > 0: return 0
        else: return idx + 1
    
    def propagate_changes(self, idx: int):
        while idx > 1:
            idx //= 2
            self.update_node(idx)
    
    
    def query(self) -> int:
        return self.sums[1]


class Solution:
    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        st = SegTree(nums1)
        sums = sum(nums2)
        results = []
        n = len(nums1)

        for qtype, arg1, arg2 in queries:
            match qtype:
                case 1: # flip segment between arg1 and arg2
                    st.update(arg1, arg2 + 1)
                    continue
                case 2: # add arg1 * sum(nums1) to sums
                    sums += arg1 * st.query()
                    continue
                case 3: # report
                    results.append(sums)
                    continue
        
        return results

47700