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

"""
[0,1,0,1,0,1,0]
[[2,1,0],[1,3],[1,5],[2,0,1],[1,3],[1,5],[2,1,1],[1,3],[1,5],[2,2,1],[1,3],[1,5],[2,3,0],[1,3],[1,5],[2,6,1],[1,3],[1,5]]
[0,1,1,0,1]
[[2,1,0],[1,4]]
[0,0,1,0,1,1]
[[1,3],[2,3,0],[1,5]]
[1,1,0,1]
[[2,1,0],[2,2,1],[1,3],[2,2,0],[1,3]]
"""

from sortedcontainers import SortedList

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        n = len(colors)
        ct = Counter()
        se = SortedList()
        s = 0
        colors.append(colors[-1])
        for i in range(n):
            if 0 == colors[i] ^ colors[i + 1]:
                e = i
                se.add(s)
                se.add(e)
                ct[e - s + 1] += 1
                s = i + 1
        colors.pop()
        # print(colors, se, ct)

        def update_e(l, r):
            s, e = se[l], se[r]
            if s < e: # original zone longer than 1
                ct[e - s + 1] -= 1
                ct[e - s] += 1
                if e == n - 1:
                    ct[1] += 1 # new length 1 end zone
                    se.update([e - 1, e]) # new zones [s, e - 1, e, e]
                else:
                    # next zone length + 1
                    ct[se[r + 2] - se[r + 1] + 1] -= 1
                    ct[se[r + 2] - e + 1] += 1
                    # [s, e, ss, ee] => [s, e - 1, e, ee]
                    se.remove(e + 1)
                    se.add(e - 1)
            else: # single element zone, messy
                # colors.length >= 4
                ct[1] -= 1
                rmv = [s, e]
                ins = [s, e]
                if s > 0:
                    ct[se[l - 1] - se[l - 2] + 1] -= 1
                    rmv += [se[l - 2], se[l - 1]]
                    ins += [se[l - 2], se[l - 1]]
                if s < n - 1:
                    ct[se[r + 2] - se[r + 1] + 1] -= 1
                    rmv += [se[r + 1], se[r + 2]]
                    ins += [se[r + 1], se[r + 2]]
                ins.sort()
                for rm in rmv:
                    se.remove(rm)
                se.add(ins[0])
                se.add(ins[-1])
                ct[ins[-1] - ins[0] + 1] += 1

        # start of a zone modified
        def update_s(l, r):
            s, e = se[l], se[r]
            ct[e - s + 1] -= 1 # remove original length
            ct[e - s] += 1 # new length [s + 1 to e]
            # originally it was a start
            # either 0 or same color as its previous
            # now new color must be different to its previous
            if not s:
                ct[1] += 1 # new length 1 start zone
                se.update([s, s + 1]) # new zones [s, s, s + 1, e]
            else:
                # previous zone length + 1
                ct[se[l - 1] - se[l - 2] + 1] -= 1
                ct[s - se[l - 2] + 1] += 1
                # [ss, ee, s, e] => [ss, s, s + 1, e]
                se.remove(s - 1)
                se.add(s + 1)

        # simplest, break one zone into 3
        def update_m(l, r, j):
            s, e = se[l], se[r]
            ct[e - s + 1] -= 1
            ct[1] += 1
            ct[j - s] += 1
            ct[e - j] += 1
            se.remove(s)
            se.remove(e)
            se.update([s, j - 1, j, j, j + 1, e])

        ans = []
        for k in range(len(queries)):
            if queries[k][0] == 1:
                res = 0
                for x in ct:
                    if x >= queries[k][1]:
                        res += ct[x] * (x + 1 - queries[k][1])
                if colors[-1] != colors[0]: # check connectable
                    # longest possible circular zone occurs if last zone
                    # is connectable with the first zone
                    # length of the first zone is limited by query
                    # length of the first zoen has the same limit
                    # both to avoid duplicate!!!
                    x = min(se[-1] - se[-2] + 1, queries[k][1] - 1) + \
                        min(se[1] - se[0] + 1, queries[k][1] - 1)
                    res += max(0, x + 1 - queries[k][1])
                ans.append(res)
            else:
                j, c = queries[k][1], queries[k][2]
                if c != colors[j]:
                    colors[j] = c
                    dx = se.bisect_right(j) - 1
                    if dx & 1: # j is an end
                        update_e(dx - 1, dx)
                    else: # j is not an end, may be start or middle
                        if j == se[dx]:
                            update_s(dx, dx + 1)
                        else:
                            update_m(dx, dx + 1, j)
        # print(colors, se, ct)

        return ans
41600