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

from sortedcontainers import SortedList

class SegTree:
    def __init__(self, n):
        self.n = n
        self.l = [0] * (n << 2)
        self.r = [0] * (n << 2)
        self.v = [0] * (n << 2)
        self.build(0, 0, n)
    
    def build(self, node, l, r):
        self.l[node], self.r[node] = l, r
        if l == r:
            return
        m = (l + r) >> 1
        self.build(node*2+1, l, m)
        self.build(node*2+2, m+1, r)
    
    def update(self, node, p, delta):
        if self.l[node] == p and self.r[node] == p:
            self.v[node] += delta
            return
        m = (self.l[node] + self.r[node]) >> 1
        if p <= m:
            self.update(node*2+1, p, delta)
        else:
            self.update(node*2+2, p, delta)
        self.v[node] = self.v[node*2+1] + self.v[node*2+2]
    
    def getsum(self, node, l, r):
        if self.l[node] == l and self.r[node] == r:
            return self.v[node]
        m = (self.l[node] + self.r[node]) >> 1
        if r <= m:
            return self.getsum(node*2+1, l, r)
        elif l > m:
            return self.getsum(node*2+2, l, r)
        else:
            return self.getsum(node*2+1, l, m) + self.getsum(node*2+2, m+1, r)
        
class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        n = len(colors)
        def length(a, b):
            return b - a + 1 if a <= b else b + n - a + 1

        start = 0
        l = SortedList()
        for i in range(1, n):
            if colors[i] == colors[i-1]:
                l.add((start, i - 1))
                start = i
        if l and colors[n-1] != colors[0]:
            l.add((start, l[0][1]))
            l.remove(l[0])
        else:
            l.add((start, n - 1))
        # print(l)
        tree1, tree2 = SegTree(n+1), SegTree(n+1)
        c = Counter([length(a, b) for a, b in l])
        for p in sorted(c, reverse=True):
            tree1.update(0, p, c[p] * p)
            tree2.update(0, p, c[p])
        
        def add(a, b):
            c = length(a, b)
            tree1.update(0, c, c)
            tree2.update(0, c, 1)
            l.add((a, b))
        
        def remove(a, b):
            c = length(a, b)
            tree1.update(0, c, -c)
            tree2.update(0, c, -1)
            l.remove((a, b))
        
        def prev(a):
            return (a - 1 + n) % n
        
        def next(a):
            return (a + 1) % n
        
        def between(x, a, b):
            return a < b and a < x < b or a > b and (a < x < n or 0 <= x < b)

        ans = []
        for query in queries:
            if query[0] == 1:
                # print(l)
                if tree2.getsum(0, n, n) == 1 and colors[l[0][0]] != colors[l[0][1]]:
                    ans.append(n)
                    continue
                size = query[1]
                ll = tree1.getsum(0, size, n)
                cnt = tree2.getsum(0, size, n)
                ans.append(ll - (size - 1) * cnt)
            else:
                idx, color = query[1:]
                if color == colors[idx]:
                    continue
                colors[idx] = color
                p = l.bisect_right((idx, inf))
                p = (p - 1 + len(l)) % len(l)
                pa, pb = l[p]
                if between(idx, pa, pb):
                    # print(query, 'if')
                    if len(l) == 1 and colors[pb] != colors[pa]:
                        add(next(idx), prev(idx))
                        add(idx, idx)
                    else:
                        add(pa, prev(idx))
                        add(idx, idx)
                        add(next(idx), pb)
                    remove(pa, pb)
                    colors[idx] = color
                elif l[p][0] != l[p][1]:
                    # print(query, 'elif', l, p, l[p])
                    if idx == l[p][0]:
                        if len(l) == 1 and color != colors[pb]:
                            add(next(idx), idx)
                            remove(pa, pb)
                            continue
                        pp = (p-1+len(l))%len(l)
                        pda, pdb = l[pp]
                        if colors[pdb] != color:
                            add(pda, idx)
                            remove(pda, pdb)
                        else:
                            add(idx, idx)
                        add(next(idx), pb)
                        remove(pa, pb)
                    else:
                        if len(l) == 1 and color != colors[pa]:
                            add(idx, prev(idx))
                            remove(pa, pb)
                            continue
                        pp = (p+1)%len(l)
                        nda, ndb = l[pp]
                        if colors[nda] != color:
                            add(idx, ndb)
                            remove(nda, ndb)
                        else:
                            add(idx, idx)
                        add(pa, prev(pb))
                        remove(pa, pb)
                else:
                    # print(query)
                    pp, pn = (p-1+len(l))%len(l), (p+1)%len(l)
                    pda, pdb = l[pp]
                    nda, ndb = l[pn]
                    if len(l) > 2 and color != colors[pdb] and color != colors[nda]:
                        add(pda, ndb)
                        remove(nda, ndb)
                        remove(pda, pdb)
                        remove(idx, idx)
                    elif color != colors[pdb]:
                        # print(query)
                        add(pda, idx)
                        remove(pda, pdb)
                        remove(idx, idx)
                    elif color != colors[nda]:
                        add(idx, ndb)
                        remove(nda, ndb)
                        remove(idx, idx)
        return ans
46000