<p>There are some red and blue tiles arranged circularly. You are given an array of integers <code>colors</code> and a 2D integers array <code>queries</code>.</p>

<p>The color of tile <code>i</code> is represented by <code>colors[i]</code>:</p>

<ul>
	<li><code>colors[i] == 0</code> means that tile <code>i</code> is <strong>red</strong>.</li>
	<li><code>colors[i] == 1</code> means that tile <code>i</code> is <strong>blue</strong>.</li>
</ul>

<p>An <strong>alternating</strong> group is a contiguous subset of tiles in the circle with <strong>alternating</strong> colors (each tile in the group except the first and last one has a different color from its <b>adjacent</b> tiles in the group).</p>

<p>You have to process queries of two types:</p>

<ul>
	<li><code>queries[i] = [1, size<sub>i</sub>]</code>, determine the count of <strong>alternating</strong> groups with size <code>size<sub>i</sub></code>.</li>
	<li><code>queries[i] = [2, index<sub>i</sub>, color<sub>i</sub>]</code>, change <code>colors[index<sub>i</sub>]</code> to <code>color<font face="monospace"><sub>i</sub></font></code>.</li>
</ul>

<p>Return an array <code>answer</code> containing the results of the queries of the first type <em>in order</em>.</p>

<p><strong>Note</strong> that since <code>colors</code> represents a <strong>circle</strong>, the <strong>first</strong> and the <strong>last</strong> tiles are considered to be next to each other.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">colors = [0,1,1,0,1], queries = [[2,1,0],[1,4]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[2]</span></p>

<p><strong>Explanation:</strong></p>

<p><strong class="example"><img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-14-44.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" /></strong></p>

<p>First query:</p>

<p>Change <code>colors[1]</code> to 0.</p>

<p><img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-20-25.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" /></p>

<p>Second query:</p>

<p>Count of the alternating groups with size 4:</p>

<p><img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-25-02-2.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" /><img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-24-12.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" /></p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">colors = [0,0,1,0,1,1], queries = [[1,3],[2,3,0],[1,5]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[2,0]</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-35-50.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" /></p>

<p>First query:</p>

<p>Count of the alternating groups with size 3:</p>

<p><img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-37-13.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" /><img alt="" data-darkreader-inline-bgcolor="" data-darkreader-inline-bgimage="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-from-2024-06-03-20-36-40.png" style="width: 150px; height: 150px; padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; --darkreader-inline-bgimage: initial; --darkreader-inline-bgcolor: #181a1b;" /></p>

<p>Second query: <code>colors</code> will not change.</p>

<p>Third query: There is no alternating group with size 5.</p>
</div>

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

<ul>
	<li><code>4 &lt;= colors.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= colors[i] &lt;= 1</code></li>
	<li><code>1 &lt;= queries.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>queries[i][0] == 1</code> or <code>queries[i][0] == 2</code></li>
	<li>For all <code>i</code> that:
	<ul>
		<li><code>queries[i][0] == 1</code>: <code>queries[i].length == 2</code>, <code>3 &lt;= queries[i][1] &lt;= colors.length - 1</code></li>
		<li><code>queries[i][0] == 2</code>: <code>queries[i].length == 3</code>, <code>0 &lt;= queries[i][1] &lt;= colors.length - 1</code>, <code>0 &lt;= queries[i][2] &lt;= 1</code></li>
	</ul>
	</li>
</ul>


from sortedcontainers import SortedList

# Binary Indexed Tree
# Range Update Range Query
class RBIT:
    def __init__(self, N: int):
        self.b1 = [0] * (N + 1)
        self.b2 = [0] * (N + 1)
        
    def incr(self, arr, i, x):
        while i <= len(arr):
            arr[i] += x
            i += i & -i
        
    def range_add(self, l, r, x):
        self.incr(self.b1, l, x)
        self.incr(self.b1, r + 1, -x)
        
        self.incr(self.b2, l, x * (l - 1))
        self.incr(self.b2, r + 1, -x * r)
        
    def total(self, arr, i):
        s = 0
        
        while i > 0:
            s += arr[i]
            i -= i & -i
        return s
    
    def rtotal(self, i):
        return self.total(self.b1, i) * i - self.total(self.b2, i)

# Only Update Single and Query 
class BIT:
    def __init__(self, N: int):
        self.stree = [0] * (N + 1)

    def incr(self, i, x):
        while i < len(self.stree):
            self.stree[i] += x
            i |= (i + 1)
            
    def total(self, i):
        s = 0
        
        while i >= 0:
            s += self.stree[i]
            i &= i + 1
            i -= 1
        return s

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        N = len(colors)
        INF = 10 ** 20
        
        # regular prefix sum -> update frequency table -> query from 0 to N
        prefix = BIT(N + 1)
        # triangle prefix sum -> range update -> query from 0 to N
        pprefix = RBIT(N * 2)
        
        sl = SortedList()
        sl.add((0, 0, N))

        def incr(x, v):
            prefix.incr(x, v)
            pprefix.range_add(x, N, v)
        
        incr(N, 1)
        def change(index, val):
            # find the segment index is in
            sindex = sl.bisect_right((index, INF, INF))
            
            if sindex - 1 >= 0:
                pstart, pval, vlen = sl[sindex - 1]
                if pval == val:
                    # the value didn't change, save us some work
                    return
                
                # create the piece after this piece
                if index + 1 < N:
                    if sindex < len(sl):
                        # if the piece after this piece is not existing
                        if index + 1 < sl[sindex][0]:
                            # create a new chunk
                            incr(vlen - (index - pstart) - 1, 1)
                            sl.add((index + 1, pval, vlen - (index - pstart) - 1))
                    else:
                        incr(N - index - 1, 1)
                        sl.add((index + 1, pval, N - index - 1))

                incr(vlen, -1)
                sl.remove((pstart, pval, vlen))
                if index != pstart:
                    incr(index - pstart, 1)
                    sl.add((pstart, pval, index - pstart))
                incr(1, 1)
                sl.add((index, val, 1))
            else:
                assert(False)

            # now the piece is added, but we might have to merge pieces
                
            #print("a", sl)
            # merge with the right if possible
            sindex = sl.bisect_left((index, -1, -1))
            if sindex + 1 < len(sl):
                nstart, nval, vlen = sl[sindex + 1]
                if nval == val:
                    cstart, cval, clen = sl[sindex]
                    
                    incr(vlen, -1)
                    sl.remove((nstart, nval, vlen))
                    
                    incr(clen, -1)
                    sl.remove((cstart, cval, clen))
                    
                    incr(vlen + clen, 1)
                    sl.add((cstart, cval, vlen + clen))
            
            # merge with the previous piece, if it exists
            sindex = sl.bisect_left((index, -1, -1))
            
            if sindex - 1 >= 0:
                pstart, pval, vlen = sl[sindex - 1]
                nstart, nval, nlen = sl[sindex]
                if pval == nval:
                    # merge them

                    incr(vlen, -1)
                    sl.remove((pstart, pval, vlen))
                    
                    incr(nlen, -1)
                    sl.remove((nstart, nval, nlen))
                    
                    incr(vlen + nlen, 1)
                    sl.add((pstart, pval, vlen + nlen))
                    
        # O(N log N)
        for index, c in enumerate(colors):
            if colors[index] != (index % 2):
                change(index, 1)
                
        # O(Q log N) times
        
        # total time = O(N log N + Q log N)
        # total space = O(N + Q)
        ans = []
        for query in queries:
            if query[0] == 1:
                sz = query[1]
                
                row = len(sl)
                nrows = N - sz + 1
                
                count = nrows * row - pprefix.rtotal(N - 1) + pprefix.rtotal(sz - 2)
                
                # first chunk
                lstart, lval, llen = sl[0]

                # last chunk
                rstart, rval, rlen = sl[-1]

                if (N % 2 == 0) == (lval == rval):
                    count += min(max(llen + rlen - sz + 1, 0), llen, rlen, sz - 1)

                ans.append(count)
            else:
                index, color = query[1], query[2]
                
                if color == index % 2:
                    change(index, 0)
                else:
                    change(index, 1)
                
        return ans
                
        
        
        
        

42300