<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, colors: list[int], queries: list[list[int]]) -> list[int]:
        def get_legnth(region: tuple[int, int]) -> int:
            """Return the length of the range represented by region.
            """
            if region[0] <= region[1]:
                return region[1] - region[0] + 1
            else:
                return len(colors) - region[0] + region[1] + 1
        max_alt_groups = SortedList()
        count = [0 for _ in range(len(colors))]
        start = 0
        for i in range(1, len(colors)):
            if colors[i] == colors[i - 1]:
                count[i - start - 1] += 1
                max_alt_groups.add((start, i - 1))
                start = i
        max_alt_groups.add((start, len(colors) - 1))
        count[len(colors) - start - 1] += 1
        around = colors[0] != colors[-1]
        is_ring = (len(max_alt_groups) == 1) and (colors[max_alt_groups[0][0]] != colors[max_alt_groups[0][1]])
        if around and not is_ring:
            count[max_alt_groups[0][1] - max_alt_groups[0][0] + max_alt_groups[-1][1] - max_alt_groups[-1][0] + 1] += 1
            count[max_alt_groups[0][1] - max_alt_groups[0][0]] -= 1
            count[max_alt_groups[-1][1] - max_alt_groups[-1][0]] -= 1
            end = max_alt_groups.pop()
            first = max_alt_groups.pop(0)
            max_alt_groups.add((end[0], first[1]))
        is_ring = (len(max_alt_groups) == 1) and (colors[max_alt_groups[0][0]] != colors[max_alt_groups[0][1]])
        count_tree, size_tree = BinaryIndexedTree(count), BinaryIndexedTree([c * (j + 1) for j, c in enumerate(count)])
        res = []
        for query in queries:
            if query[0] == 1:
                if is_ring:
                    res.append(len(colors))
                else:
                    cur_count = count_tree.prefix_sum_query(len(colors)) - count_tree.prefix_sum_query(query[1] - 1)
                    cur_size = size_tree.prefix_sum_query(len(colors)) - size_tree.prefix_sum_query(query[1] - 1)
                    res.append(cur_size - cur_count * (query[1] - 1))
            else:
                index, color = query[1], query[2]
                if color != colors[index]:
                    colors[index] = color
                    if (colors[index] != colors[(index - 1) % len(colors)]) and \
                            (colors[index] != colors[(index + 1) % len(colors)]):
                        if len(max_alt_groups) <= 2:
                            max_alt_groups.pop()
                            max_alt_groups.pop()
                            max_alt_groups.add((0, len(colors) - 1))
                            count_tree.update(1, -1)
                            count_tree.update(len(colors) - 1, -1)
                            count_tree.update(len(colors), 1)
                            size_tree.update(1, -1)
                            size_tree.update(len(colors) - 1, -len(colors) + 1)
                            size_tree.update(len(colors), len(colors))
                        else:
                            pos = max_alt_groups.bisect_left((index, index))
                            if pos == 0:
                                left = max_alt_groups.pop(-1)
                                max_alt_groups.pop(0)
                                right = max_alt_groups.pop(0)
                            elif pos == len(max_alt_groups) - 1:
                                right = max_alt_groups.pop(0)
                                max_alt_groups.pop()
                                left = max_alt_groups.pop()
                            else:
                                left = max_alt_groups.pop(pos - 1)
                                max_alt_groups.pop(pos - 1)
                                right = max_alt_groups.pop(pos - 1)
                            max_alt_groups.add((left[0], right[1]))
                            left_len = get_legnth(left)
                            right_len = get_legnth(right)
                            count_tree.update(1, -1)
                            count_tree.update(left_len, -1)
                            count_tree.update(right_len, -1)
                            count_tree.update(left_len + right_len + 1, 1)
                            size_tree.update(1, -1)
                            size_tree.update(left_len, -left_len)
                            size_tree.update(right_len, -right_len)
                            size_tree.update(left_len + right_len + 1, left_len + right_len + 1)
                    elif colors[index] != colors[(index + 1) % len(colors)]:
                        if len(max_alt_groups) == 1:
                            block = max_alt_groups.pop()
                            max_alt_groups.add(((block[0] - 1) % len(colors), (block[1] - 1) % len(colors)))
                        else:
                            pos = max_alt_groups.bisect_right((index + 1, -1))
                            if (pos == len(max_alt_groups)) or (pos == 0):
                                left = max_alt_groups.pop(pos - 1)
                                right = max_alt_groups.pop(0)
                            else:
                                left = max_alt_groups.pop(pos - 1)
                                right = max_alt_groups.pop(pos - 1)
                            max_alt_groups.add((left[0], (left[1] - 1) % len(colors)))
                            max_alt_groups.add(((right[0] - 1) % len(colors), right[1]))
                            left_len = get_legnth(left)
                            right_len = get_legnth(right)
                            count_tree.update(left_len, -1)
                            count_tree.update(right_len, -1)
                            count_tree.update(left_len - 1, 1)
                            count_tree.update(right_len + 1, 1)
                            size_tree.update(left_len, -left_len)
                            size_tree.update(right_len, -right_len)
                            size_tree.update(left_len - 1, left_len - 1)
                            size_tree.update(right_len + 1, right_len + 1)
                    elif colors[index] != colors[(index - 1) % len(colors)]:
                        if len(max_alt_groups) == 1:
                            block = max_alt_groups.pop()
                            max_alt_groups.add(((block[0] + 1) % len(colors), (block[1] + 1) % len(colors)))
                        else:
                            pos = max_alt_groups.bisect_left((index, -1))
                            if pos == 0:
                                left = max_alt_groups.pop()
                                right = max_alt_groups.pop(0)
                            else:
                                left = max_alt_groups.pop(pos - 1)
                                right = max_alt_groups.pop(pos - 1)
                            max_alt_groups.add((left[0], (left[1] + 1) % len(colors)))
                            max_alt_groups.add(((right[0] + 1) % len(colors), right[1]))
                            left_len = get_legnth(left)
                            right_len = get_legnth(right)
                            count_tree.update(left_len, -1)
                            count_tree.update(right_len, -1)
                            count_tree.update(left_len + 1, 1)
                            count_tree.update(right_len - 1, 1)
                            size_tree.update(left_len, -left_len)
                            size_tree.update(right_len, -right_len)
                            size_tree.update(left_len + 1, left_len + 1)
                            size_tree.update(right_len - 1, right_len - 1)
                    else:
                        if is_ring:
                            max_alt_groups.pop()
                            max_alt_groups.update([(index, index),
                                                   ((index + 1) % len(colors), (index - 1) % len(colors))])
                            count_tree.update(len(colors), -1)
                            count_tree.update(1, 1)
                            count_tree.update(len(colors) - 1, 1)
                            size_tree.update(len(colors), -len(colors))
                            size_tree.update(1, 1)
                            size_tree.update(len(colors) - 1, len(colors) - 1)
                        else:
                            pos = max_alt_groups.bisect_right((index, -1))
                            block = max_alt_groups.pop(pos - 1)
                            max_alt_groups.update([(block[0], (index - 1) % len(colors)),
                                                   (index, index),
                                                   ((index + 1) % len(colors), block[1])])
                            block_len = get_legnth(block)
                            left_len = get_legnth((block[0], (index - 1) % len(colors)))
                            right_len = get_legnth(((index + 1) % len(colors), block[1]))
                            count_tree.update(block_len, -1)
                            count_tree.update(left_len, 1)
                            count_tree.update(1, 1)
                            count_tree.update(right_len, 1)
                            size_tree.update(block_len, -block_len)
                            size_tree.update(left_len, left_len)
                            size_tree.update(1, 1)
                            size_tree.update(right_len, right_len)
                    is_ring = (len(max_alt_groups) == 1) and \
                              (colors[max_alt_groups[0][0]] != colors[max_alt_groups[0][1]])
        return res


class BinaryIndexedTree:
    """An implementation of binary indexed tree.
    """
    def __init__(self, arr: list[int]) -> None:
        """Preconditions:
            - len(arr) > 0
        """
        self._nodes = []
        prefix_sums = [0]
        for val in arr:
            prefix_sums.append(prefix_sums[-1] + val)
        for i in range(len(prefix_sums)):
            self._nodes.append(prefix_sums[i] - prefix_sums[i - (i & (-i))])

    def __len__(self) -> int:
        return len(self._nodes) - 1

    def update(self, index: int, diff: int) -> None:
        """Change the value at the index in the ARRAY represented by this tree by diff.
        Preconditions:
            - 1 <= index <= len(self)
        """
        while index < len(self._nodes):
            self._nodes[index] += diff
            index += index & (-index)

    def prefix_sum_query(self, index: int) -> int:
        """Return the prefix sum of the ARRAY at index inclusive.
        Preconditons:
            - 1 <= index <= len(self)
        """
        res = 0
        while index > 0:
            res += self._nodes[index]
            index -= index & (-index)
        return res

42400