<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 Solution:
    def numberOfAlternatingGroups(self, c: List[int], queries: List[List[int]]) -> List[int]:
        def size(i, j):
            return j - i + 1 if i <= j else j + n - i + 1

        n = len(c)
        i = 0
        a = []
        while i < n:
            j = i
            while (i + 1) % n != j and c[i] != c[(i + 1) % n]:
                i = (i + 1) % n
            a.append([j, i])
            if i < j:
                break
            i += 1
        if a[-1][1] < a[-1][0]:
            a[0][0] = a[-1][0]
            a.pop()

        

        m = 1
        while m < n:
            m <<= 1
        
        m2 = m << 1
        b = [0] * m2
        d = [0] * m2

        def up(i, dt):
            i += m
            b[i] += dt
            d[i] += (i + 1 - m) * dt
            while i > 1:
                i >>= 1
                b[i] = b[i << 1] + b[(i << 1) + 1]
                d[i] = d[i << 1] + d[(i << 1) + 1]
        
        def qu(i, j):
            i += m
            j += m
            ans = [0, 0]
            while i <= j:
                if i & 1:
                    ans[0] += b[i]
                    ans[1] += d[i]
                    i += 1
                if j & 1 == 0:
                    ans[0] += b[j]
                    ans[1] += d[j]
                    j -= 1
                i >>= 1
                j >>= 1
            return ans

        def add(i, j):
            s = size(i, j)
            up(s - 1, 1)
            sl.add([i, j])
        
        def pop(k):
            i, j = sl.pop(k)
            s = size(i, j)
            up(s - 1, -1)
            return i, j
        
        def get(i):
            if i < sl[0][0]:
                return pop(len(sl) - 1)
            k = sl.bisect_right([i, inf]) - 1
            return pop(k)
        
        for i, j in a:
            up(size(i, j) - 1, 1)
        sl = SortedList(a)

        ans = []
        for q in queries:
            if q[0] == 1:
                if len(sl) == 1 and n & 1 == 0:
                    ans.append(n)
                else:
                    i, j = qu(q[1] - 1, n - 1)
                    ans.append(j + i - i * q[1])
                continue
            
            if c[q[1]] == q[2]:
                continue
            
            c[q[1]] = q[2]
            if len(sl) == 1 and n & 1 == 0:
                pop(0)
                add(q[1], q[1])
                add((q[1] + 1) % n, (q[1] - 1) % n)
            else:
                i, j = get(q[1])
                if i != q[1]:
                    add(i, (q[1] - 1) % n)
                add(q[1], q[1])
                if q[1] != j:
                    add((q[1] + 1) % n, j)
            
            i, j = get(q[1])
            if c[j] != c[(j + 1) % n]:
                _, j = get((j + 1) % n)
            if c[i] != c[(i - 1) % n] and sl and j != (i - 1) % n:
                i, _ = get((i - 1) % n)
            add(i, j)

            if len(sl) > 1 and c[sl[-1][1]] != c[sl[0][0]]:
                _, j = pop(0)
                i, _ = pop(len(sl) - 1)
                add(i, j)
        
        return ans
41200