<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 Solution:
    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        n = len(colors)
        
        """
        初始化starts数组。
        starts数组写的是每个交替段的开始位置和长度。
        如果有跨越起点0位置的交替段，则算的是末尾的位置。
        """
        base = 0
        starts = []
        for i in range(1, n) :
            if colors[i] == colors[i-1] :
                lent = (i-1) - base + 1
                if lent >= 3 :
                    starts.append([base, lent])
                base = i
        lent = (n-1) - base + 1
        if lent >= 3 :
            starts.append([base, lent])
        
        # circle_mark标记是否整体是一个交替环。
        circle_mark = False
        if len(starts) ==1 and starts[0][1] == n and n % 2 == 0:
            circle_mark = True

        # 处理首尾的区间合并的点，前提是尾巴有一个到末尾的。
        if not circle_mark and len(starts) and starts[-1][0]+starts[-1][1] == n and not colors[0] == colors[-1]:
            if starts[0][0] == 0 :
                starts[-1][1] += starts[0][1]
                starts.pop(0)
            else :
                for i in range(3) :
                    if not colors[i] == colors[i-1] :
                        starts[-1][1] += 1
                    else :
                        break
        # 看下开头的区间能不能合并过来
        elif not circle_mark and len(starts) and starts[0][0] == 0 :
            while not colors[starts[0][0]] == colors[starts[0][0]-1] :
                starts[0][0] -= 1
                starts[0][1] += 1
            if starts[0][0] < 0 :
                starts[0][0] += n
                starts.append(starts[0])
                starts.pop(0)
        # 看看跨越0的位置能不能弄出新的来，但长度理论上不超过4
        elif not colors[0] == colors[-1] :
            s, e = -1, 0
            if not colors[-1] == colors[-2] :
                s = -2
            if not colors[0] == colors[1] :
                e = 1
            lent = e - s + 1
            if lent >= 3 :
                starts.append([s+n, lent])


        # 对starts中所有段的长度做counter，这个也是要维护+遍历的。
        counter = collections.Counter([t[1] for t in starts])
        to_ret = []
        for qt in queries :
            # print('start', starts, circle_mark)
            # 对于查询类型，去遍历counter列表。
            if qt[0] == 1 :
                size = qt[1]
                if circle_mark :
                    to_ret.append(n)
                else :
                    rett = 0
                    for kt in counter :
                        if kt >= size :
                            rett += (kt-size+1) * counter[kt]
                    to_ret.append(rett)
            else :
                it, ct = qt[1], qt[2]
                # 如果颜色不修改，则不做任何操作。
                if colors[it] == ct :
                    continue
                need_additional_deal = False
                colors[it] = ct
                
                post_start_i = bisect.bisect(starts, [it+.1])
                pre_start_i = post_start_i - 1
                # 情况1，如果starts中没有任何段
                if len(starts) == 0 :
                    # print('branch-1')
                    s = e = it
                    while not colors[s-1] == colors[s]:
                        s -= 1
                        if s == -n+1 :
                            break
                    while not colors[(e+1)%n] == colors[e%n] :
                        e += 1
                    lent = e - s + 1 
                    if lent >= 3 :
                        starts.append([s % n, lent])
                        counter[lent] += 1
                    if len(starts) and starts[0][1] >= n :
                        starts[0][1] = n
                        circle_mark = True
                    need_additional_deal=False
                # 圆形的要做特殊处理，否则会被包含进情况2错误处理
                elif circle_mark :
                    # print('branch-2')
                    starts = [[it+1, n-1]]
                    counter = collections.Counter({n-1:1})
                # 情况2，节点如果被最后一段(环形包起点)包含：
                elif starts[-1][0] <= it + n < starts[-1][0] + starts[-1][1] or starts[-1][0] <= it < starts[-1][0] + starts[-1][1] :
                    # print('branch-3')
                    if it == starts[-1][0] or it == (starts[-1][0] + starts[-1][1]-1) % n :
                        need_additional_deal=True

                    counter[starts[-1][1]] -= 1
                    span0 = [starts[-1][0], (it-starts[-1][0]) % n]
                    span1 = [(it+1)%n, (starts[-1][0] + starts[-1][1] - it-1)%n]
                    starts.pop(-1)
                    if span0[1] >= 3 :
                        counter[span0[1]] += 1
                        starts.insert(bisect.bisect(starts, span0), span0)
                    if span1[1] >= 3 :
                        counter[span1[1]] += 1
                        starts.insert(bisect.bisect(starts, span1), span1)
                # 情况3，节点如果被前一段(非环形)包含：
                elif pre_start_i >= 0 and starts[pre_start_i][0] <= it < starts[pre_start_i][0] + starts[pre_start_i][1] :
                    # print('branch-4')
                    if it == starts[pre_start_i][0] or it == starts[pre_start_i][0] + starts[pre_start_i][1] - 1 :
                        need_additional_deal = True
                    span0 = [starts[pre_start_i][0], it-starts[pre_start_i][0]]
                    span1 = [it+1, starts[pre_start_i][0] + starts[pre_start_i][1] - it-1]
                    counter[starts[pre_start_i][1]] -= 1
                    starts.pop(pre_start_i)
                    if span1[1] >= 3 :
                        counter[span1[1]] += 1
                        starts.insert(pre_start_i, span1)
                    if span0[1] >= 3 :
                        counter[span0[1]] += 1
                        starts.insert(pre_start_i, span0)
                else :
                    need_additional_deal=True

                # 不管是最初，修改的点就在外面，还是节点在边缘且被包含，都需要同样的节点上下文处理。
                if need_additional_deal :
                    # print('need_additional_deal')

                    post_start_i = bisect.bisect(starts, [it+.1])
                    pre_start_i = post_start_i - 1
                    if len(starts) :
                        post_start_i = post_start_i % len(starts)
                    cat_post = cat_pre = False
                    if len(starts) and (starts[post_start_i][0]-1)%n == it and not colors[it] == colors[(it+1)%n] :
                        cat_post = True
                    if len(starts) and (starts[pre_start_i][0]+starts[pre_start_i][1])%n == it and not colors[it] == colors[it-1] :
                        cat_pre = True
                    
                    if cat_pre and cat_post :
                        # print('additional-branch-1')
                        if len(starts) == 1 :
                            circle_mark = True
                            starts[0][1] = n
                        else :
                            counter[starts[pre_start_i][1]] -= 1
                            counter[starts[post_start_i][1]] -= 1
                            new_span = starts[pre_start_i]
                            new_span[1] += starts[post_start_i][1] + 1
                            counter[new_span[1]] += 1
                            p1 = min(pre_start_i, post_start_i)
                            p2 = max(pre_start_i, post_start_i)
                            starts.pop(p2)
                            starts.pop(p1)
                            starts.insert(bisect.bisect(starts, new_span), new_span)
                    elif cat_pre :
                        # print('additional-branch-2')
                        counter[starts[pre_start_i][1]] -= 1
                        pit = it
                        while starts[pre_start_i][1] < n and not colors[(pit)%n] == colors[(pit-1)%n] :
                            pit += 1
                            starts[pre_start_i][1] += 1
                        counter[starts[pre_start_i][1]] += 1
                        to_add = starts[pre_start_i]
                        starts.pop(pre_start_i)
                        starts.insert(bisect.bisect(starts, to_add), to_add)
                    elif cat_post :
                        # print('additional-branch-3')
                        counter[starts[post_start_i][1]] -= 1
                        pit = it
                        while starts[post_start_i][1] < n and not colors[(pit)%n] == colors[(pit+1)%n] :
                            pit -= 1
                            starts[post_start_i][0] -= 1
                            starts[post_start_i][1] += 1
                        starts[post_start_i][0] = starts[post_start_i][0] % n
                        counter[starts[post_start_i][1]] += 1
                        to_add = starts[post_start_i]
                        starts.pop(post_start_i)
                        starts.insert(bisect.bisect(starts, to_add), to_add)
                    else :
                        # print('additional-branch-4')
                        s, e = it, it
                        while not colors[s] == colors[s-1] and (e-s+1)<=n:
                            s -= 1
                        while not colors[e%n] == colors[(e+1)%n] and (e-s+1)<=n:
                            e += 1
                        to_add = [s%n, e-s+1]
                        starts.insert(bisect.bisect(starts, to_add), to_add)
                        counter[e-s+1] += 1

                if len(starts) == 1 and starts[0][1] >= n and n % 2 == 0 :
                    circle_mark = True
                else :
                    circle_mark = False
        
        return to_ret
39700