<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 TreeNode:
    def __init__(self):
        self.val = 0
        self.chd = collections.defaultdict(TreeNode)

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        from sortedcontainers import SortedList
        n = len(colors)
        bars = [i for i in range(n) if colors[(i - 1) % n] == colors[i % n]]
        
        # Implement Fenwick trees for storing the counts and total sizes of the alternating groups by size
        nbits = 16
        ct_ = TreeNode()
        sz_ = TreeNode()
        
        def add_val(root: TreeNode, ind: int, delta: int) -> None:
            ptr = root
            for i in range(nbits - 1, -1, -1):
                if ind & (1 << i):
                    ptr = ptr.chd[i]
                else:
                    ptr.chd[i].val += delta
        
        def get_sum(root: TreeNode, ub: int) -> int: # including ub
            ub += 1
            ptr = root
            ret = 0
            for i in range(nbits - 1, -1, -1):
                if ub & (1 << i):
                    ret += ptr.chd[i].val
                    ptr = ptr.chd[i]
            
            return ret
        
        def get_range_sum(root: TreeNode, lb: int, ub: int) -> int: # including both lb and ub
            return get_sum(root, ub) - (get_sum(root, lb - 1) if lb > 0 else 0)
        
        # Initialize the Fenwick tree based on the starting colors
        if len(bars) == 0:
            add_val(ct_, n, 1)
            add_val(sz_, n, n)
        else:
            for i in range(len(bars) - 1):
                tmp = bars[i + 1] - bars[i]
                add_val(ct_, tmp, 1)
                add_val(sz_, tmp, tmp)
            tmp = (bars[0] + n) - bars[-1]
            add_val(ct_, tmp, 1)
            add_val(sz_, tmp, tmp)
        
        bars = SortedList(bars)
        
        # Define operations for adding and removing bars
        def add_bar(ind: int) -> None:
            #print(f"Add bar at index {ind}")
            loc = bars.bisect_left(ind)
            bars.add(ind)
            
            if (nb := len(bars)) > 1:
                lnbr = bars[(loc - 1) % nb]
                rnbr = bars[(loc + 1) % nb]
                if lnbr >= ind:
                    lnbr -= n
                if rnbr <= ind:
                    rnbr += n
                #print(lnbr, ind, rnbr)
                
                l_gap = ind - lnbr
                r_gap = rnbr - ind
                ttl_gap = rnbr - lnbr
                add_val(ct_, l_gap, 1)
                add_val(sz_, l_gap, l_gap)
                add_val(ct_, r_gap, 1)
                add_val(sz_, r_gap, r_gap)
                add_val(ct_, ttl_gap, -1)
                add_val(sz_, ttl_gap, -ttl_gap)
        
        def rmv_bar(ind: int) -> None:
            #print(f"Remove bar at index {ind}")
            loc = bars.bisect_left(ind)
            if (nb := len(bars)) > 1:
                lnbr = bars[(loc - 1) % nb]
                rnbr = bars[(loc + 1) % nb]
                if lnbr >= ind:
                    lnbr -= n
                if rnbr <= ind:
                    rnbr += n
                #print(lnbr, ind, rnbr)
                
                l_gap = ind - lnbr
                r_gap = rnbr - ind
                ttl_gap = rnbr - lnbr
                add_val(ct_, l_gap, -1)
                add_val(sz_, l_gap, -l_gap)
                add_val(ct_, r_gap, -1)
                add_val(sz_, r_gap, -r_gap)
                add_val(ct_, ttl_gap, 1)
                add_val(sz_, ttl_gap, ttl_gap)
                
            bars.remove(ind)
        
        ans = []
        #print('*', bars)
        
        for q in queries:
            if q[0] == 1:
                qsz = q[1]
                if len(bars) == 0:
                    ans.append(n)
                else:
                    ans.append(get_range_sum(sz_, qsz, n) - get_range_sum(ct_, qsz, n) * (qsz - 1))
            else:
                ind = q[1]
                clr = q[2]
                
                if colors[ind] == clr:
                    continue
                
                colors[ind] = clr
                for i in range(ind, ind + 2):
                    if colors[(i - 1) % n] == colors[i % n]:
                        add_bar(i % n)
                    else:
                        rmv_bar(i % n)
            #print('*', bars)
        
        return ans
    
43900