<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>

class LazySegmentTree: 
    
    def __init__(self, nums):
        self.h = len(nums).bit_length()
        self.n = 1 << self.h
        self.tree = self._build(nums)
        self.lazy = [0]*len(self.tree)
        
    def _build(self, nums):
        n = self.n
        tree = [0]*(2*n)
        tree[n:n+len(nums)] = nums
        # now work backwards to calculate sums
        for i in range(n-1, 0, -1):
            tree[i] = tree[i*2] + tree[i*2 + 1]
        # actual tree starts from index 1
        return tree
    
    def _level(self, ind):
        # For example 4 5 6 7 is level 2
        return ind.bit_length() - 1

    def _numLeaves(self, ind):
        # how many leaves in the subtree
        return 2 ** (self.h - self._level(ind))
    
    def _leafRange(self, ind):
        # range of leaves belonging to this subtree
        leaves = self._numLeaves(ind)
        offset = ind * leaves
        return (offset, offset + leaves)
    
    def _isLeaf(self, ind):
        # we organized our tree that way
        return ind >= self.n
    
    def flipBit(self, i):
        return 1 - i
    
    def _flipSum(self, i, leafNum):
        # Updates sum of node with index i and propagate up
        diff = leafNum - 2*self.tree[i]
        j = i
        while j > 0:
            self.tree[j] += diff
            j //= 2 # move up the tree
            
    def _pushLazyDown(self, i, leafNum):
        # Update the node value and move lazy flag down the tree
        self.tree[i] = leafNum - self.tree[i]
        self.lazy[i] = 0
        # if not leaf then push lazyness to leaves
        if not self._isLeaf(i):
            self.lazy[2*i] = self.flipBit(self.lazy[2*i])
            self.lazy[2*i + 1] = self.flipBit(self.lazy[2*i + 1])
    
    def flip(self, l, r):
        def isIntersecting(range1, range2):
            return not (range1[1] <= range2[0] or range2[1] <= range1[0])
    
        def isCovered(range1, range2):
            return range1[0] >= range2[0] and range1[1] <= range2[1]
        
        def flipAtNode(i, interval, leaves):
            if self.lazy[i]:
                self._pushLazyDown(i, leaves[1] - leaves[0])
            if self._isLeaf(i):
                if interval[0]<=i<interval[1]:
                    self._flipSum(i, leaves[1] - leaves[0])
                return
            
            if not isIntersecting(leaves, interval):
                return
            if isCovered(leaves, interval):
                self._flipSum(i, leaves[1] - leaves[0])
                self.lazy[i*2] = self.flipBit(self.lazy[i*2])
                self.lazy[2*i + 1] = self.flipBit(self.lazy[2*i + 1])
            else:
                mid = (leaves[0] + leaves[1])//2
                flipAtNode(i*2, interval, (leaves[0], mid))
                flipAtNode(i*2 + 1, interval, (mid, leaves[1]))
            
        flipAtNode(1, (l + self.n, r + self.n), (self.n, 2*self.n))
            
    def sum(self):
        return self.tree[1]



class Solution:
    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        self.nums1 = nums1
        self.nums2 = nums2
        self.n = len(nums1)
        self.nums2_sum = sum(nums2)
        self.segmentTree = LazySegmentTree(nums1)

        result = []
        for query in queries:
            x, y, z = query
            if x == 1:
                self.segmentTree.flip(y, z + 1)
            elif x == 2:
                self.nums2_sum += self.segmentTree.sum() * y
            else:
                result.append(self.nums2_sum)
        return result
        

51500