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

class SegTree:
    def __init__(self,vals,merge):        
        self.merge = lambda a,b: b if a==None else a if b==None else merge(a,b)
        self.n = 1<<(len(vals)-1).bit_length()
        self.tree = [None]*(self.n*2) # tree[0] is dummy. Root start from tree[1]
        self.setMany(0,vals)
    def rootVal(self): return self.tree[1]
    def add(self,i): 
        a,b = self.tree[i+self.n]
        self.set(i,[a+1,b+i])
    def remove(self,i):
        a,b = self.tree[i+self.n]
        self.set(i,[a-1,b-i])
    def getVals(self): return self.tree[self.n:]
    def getMany(self,i,j): return self.tree[i+self.n:j+self.n+1]
    def set(self,i,v): self.setMany(i,[v])
    def setMany(self,i,vals): # set many vals starting from i
        i,j=i+self.n, i+len(vals)-1+self.n
        self.tree[i:j+1] = vals
        while i>1:
            i,j = i//2,j//2
            for k in range(i,j+1):
                self.tree[k] = self.merge(self.tree[2*k], self.tree[2*k+1])
    def query(self,i,j): # [i,j] inclusive
        i,j = i+self.n, j+self.n
        res1,res2 = None,None
        while i<=j:
            if i & 1:
                res1 = self.merge(res1,self.tree[i]) # merge param order matter
                i += 1
            if not j & 1:
                res2 = self.merge(self.tree[j],res2) # merge param order matter
                j -= 1                
            i,j = i//2,j//2
        return self.merge(res1,res2)

from sortedcontainers import SortedList
class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        # segment trees stores frequency of alternating length, using bucket sort to handle add/delete
        # merge first and last group into one group

        n = len(colors)

        # init all colors to 0.
        # posSegs[i] = [start_idx, end_idx]
        posSegs = SortedList([[i,i] for i in range(n)])

        # vals[ln] = [cnt,sm]: alternating ln=5 has cnt=11 items, sm=5*11
        vals = [[0,0] for i in range(n+1)]
        vals[1] = [n,n] # ln == 1, [cnt == n, sm*cnt == n]
        freqSegs = SegTree(vals,lambda a,b: [a[0]+b[0],a[1]+b[1]])

        # merge first and last group into one group
        def addSeg(start_i,end_i):
            # start_i must < n, end_i can > n
            start_i,end_i = start_i%n,end_i%n
            if end_i<start_i: end_i += n
            posSegs.add([start_i,end_i])
            freqSegs.add(end_i-start_i+1)
        def removeSeg(start_i,end_i):
            # use 'remove' instead of 'pop' to avoid delete overlapping
            posSegs.remove([start_i,end_i])
            freqSegs.remove(end_i-start_i+1)
        def updateIsCircle():
            nonlocal isCircle
            if len(posSegs)==1:
                start_i,end_i = posSegs[0]
                isCircle = (end_i+1)%n==start_i%n \
                    and colors2[start_i%n]!=colors2[end_i%n]
            else:
                isCircle = False

        isCircle = False
        colors2 = [0]*n
        def changeColor(i,c): # set colors[i] = c
            if colors2[i]==c:
                return

            # in case of single head-end linked circle
            if isCircle:
                start_i,end_i = posSegs[0] 
                removeSeg(start_i,end_i)
                addSeg(i,i)
                addSeg(i+1,i-1+n)
                colors2[i]=c
                updateIsCircle()
                return
            
            ii = posSegs.bisect_right([i,math.inf])-1
            start_i,end_i = posSegs[ii % len(posSegs)]
            prev_start_i,prev_end_i = posSegs[(ii-1)%len(posSegs)]
            nxt_start_i,nxt_end_i = posSegs[(ii+1)%len(posSegs)]
            removeSeg(start_i,end_i)

            if i<start_i: 
                i+=n # to make sure 'start_i <= i <= end_i'
            if start_i<i<end_i:
                addSeg(start_i,i-1)
                addSeg(i,i)
                addSeg(i+1,end_i)
            elif i==start_i and i==end_i:
                removeSeg(prev_start_i,prev_end_i)
                if not posSegs: # ...group1) + one dot + (group1...
                    addSeg(0,n-1) # turn to single circle
                else:
                    removeSeg(nxt_start_i,nxt_end_i)
                    addSeg(prev_start_i,nxt_end_i)
            elif i==start_i:
                if not posSegs: # single group but not head-end linked
                    addSeg(start_i+1,end_i+1)
                else:
                    removeSeg(prev_start_i,prev_end_i)
                    addSeg(prev_start_i,prev_end_i+1)
                    addSeg(start_i+1,end_i)
            elif i==end_i:
                if not posSegs: # single group but not head-end linked
                    addSeg(start_i-1,end_i-1)
                else:
                    removeSeg(nxt_start_i,nxt_end_i)
                    addSeg(start_i,end_i-1)
                    addSeg(end_i,nxt_end_i)
            colors2[i%n]=c
            updateIsCircle()

        for i,c in enumerate(colors):
            changeColor(i,c)
        res = []
        for q in queries:
            if q[0]==1:
                size = q[1]
                if isCircle:
                    res.append(n)
                else:
                    cnt,sm = freqSegs.query(size,n)
                    res.append(sm-cnt*(size-1))
            elif q[0]==2:
                i,c = q[1],q[2]
                changeColor(i,c)
        return res
43200