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

import sortedcontainers
class CntSegmTree:
    def __init__(self, min_length, max_length):
        self.max_length = max_length 
        self.min_length = min_length
        self.cnt = 0
        self.total = 0
        self.right = None
        self.left = None

    def add(self, length):
        self.cnt+=1
        self.total+=length
        if self.max_length==self.min_length:
            return
        mid = (self.max_length+self.min_length)>>1
        if length<=mid:
            if self.left is None:
                self.left = CntSegmTree(self.min_length, mid)
            self.left.add(length)
        else:
            if self.right is None:
                self.right = CntSegmTree(mid+1, self.max_length)
            self.right.add(length)
    
    def remove(self, length):
        self.cnt-=1
        self.total-=length
        if self.max_length==self.min_length:
            return
        mid = (self.max_length+self.min_length)>>1
        if length<=mid:
            self.left.remove(length)
            if self.left.cnt==0:
                self.left = None
        else:
            self.right.remove(length)
            if self.right.cnt==0:
                self.right = None

    def query(self, length):
        if self.max_length==self.min_length:
            return (self.total, self.cnt)
        mid = (self.max_length+self.min_length)>>1
        if length<=mid:
            return self.left.query(length) if self.left else (0, 0)
        total, cnt = (self.left.total, self.left.cnt) if self.left else (0, 0)
        _total, _cnt = self.right.query(length) if self.right else (0, 0)
        return (total+_total, cnt+_cnt)

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        cnt_tree = CntSegmTree(0, len(colors))
        pre = 0
        sl = sortedcontainers.SortedList()
        for i, color in enumerate(colors[1:], 1):
            if color==colors[i-1]:
                sl.add(pre)
                cnt_tree.add(i-pre)
                pre = i
        sl.add(pre)
        sl.add(len(colors))
        cnt_tree.add(len(colors)-pre)
        
        res = []
        for query in queries :
            # print(sl)
            # print("--", cnt_tree.total, cnt_tree.cnt)
            if query[0]==1:
                l = query[1]-1
                
                if len(sl)==2:
                    
                    res.append(len(colors) if colors[0]!=colors[-1] else len(colors)-l)
                    continue
                total, cnt = cnt_tree.total, cnt_tree.cnt
                _total, _cnt = cnt_tree.query(l)
                # print(total, cnt, _total, _cnt)
                if colors[0]!=colors[-1]:
                    cnt -= 1
                    for _l in [sl[1], sl[-1]-sl[-2]]:
                        if _l<=l:
                            _total, _cnt = _total-_l, _cnt-1
                    if (t:=sl[1]+sl[-1]-sl[-2])<=l:
                        _total, _cnt = _total+t, _cnt+1
                # print(total, cnt, _total, _cnt)
                res.append(total-_total-l*(cnt-_cnt))
            else:
                idx, color = query[1:]
                if color==colors[idx]:
                    continue
                colors[idx] = color
                
                if idx==0:
                    if idx+1!=sl[1]:
                        cnt_tree.remove(sl[1]-idx)
                        cnt_tree.add(1), cnt_tree.add(sl[1]-1)
                        sl.add(1)
                    else:
                        cnt_tree.remove(sl[1]), cnt_tree.remove(sl[2]-sl[1])
                        cnt_tree.add(sl[2])
                        sl.remove(sl[1])
                elif idx+1==len(colors):
                    if idx!=sl[-2]:
                        cnt_tree.remove(sl[-1]-sl[-2])
                        cnt_tree.add(1), cnt_tree.add(sl[-1]-sl[-2]-1)
                        sl.add(idx)
                    else:
                        cnt_tree.remove(sl[-1]-sl[-2]), cnt_tree.remove(sl[-2]-sl[-3])
                        cnt_tree.add(sl[-1]-sl[-3])
                        sl.remove(sl[-2])
                else:
                    i = sl.bisect_right(idx)-1
                    # print("i", i)
                    if idx==sl[i]:
                        if idx+1==sl[i+1]:
                            cnt_tree.remove(1), cnt_tree.remove(sl[i+2]-sl[i+1]), cnt_tree.remove(sl[i]-sl[i-1])
                            cnt_tree.add(sl[i+2]-sl[i-1])
                            sl.remove(sl[i+1]), sl.remove(sl[i])
                        else:
                            cnt_tree.remove(sl[i]-sl[i-1]), cnt_tree.remove(sl[i+1]-sl[i])
                            cnt_tree.add(sl[i]-sl[i-1]+1), cnt_tree.add(sl[i+1]-sl[i]-1)
                            sl.remove(idx), sl.add(idx+1)
                    else:
                        if idx+1==sl[i+1]:
                            cnt_tree.remove(sl[i+1]-sl[i]), cnt_tree.remove(sl[i+2]-sl[i+1])
                            cnt_tree.add(sl[i+1]-sl[i]-1), cnt_tree.add(sl[i+2]-sl[i+1]+1)
                            sl.remove(idx+1), sl.add(idx)
                        else:
                            # print("*")
                            cnt_tree.remove(sl[i+1]-sl[i])
                            cnt_tree.add(sl[i+1]-idx-1), cnt_tree.add(1), cnt_tree.add(idx-sl[i])
                            sl.add(idx), sl.add(idx+1)



        return res


        
41400