<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]:
        group_counter = GroupCounter(colors, queries)
        ans = []
        for query in queries:
            if query[0] == 1:
                ans.append(group_counter.count_groups(query[1]))
            else:
                i = query[1]
                color = query[2]
                if (i + color) % 2 == group_counter.get(i):
                    continue
                group_counter.flip(i)
                group_counter.flip(i + len(colors))
        return ans


class GroupCounter:
    def __init__(self, colors, queries):
        values = [(i + c) % 2 for i, c in enumerate(colors + colors)]
        sizes = sorted(set(query[1] for query in queries if query[0] == 1))
        self.data = []
        acc = 0
        for val, group in itertools.groupby(values):
            size = sum(1 for _ in group)
            self.data.append([acc, val, size])
            acc += size
        self.length = len(colors)
        self.group_counts = [0 for _ in range(len(colors) + 1)]
        self.sizes = sizes
        for j in range(len(self.data)):
            self.up_count(j)
    
    def get(self, j):
        i = self._get(j)
        return self.data[i][1]
    
    def _get(self, j):
        k = bisect.bisect_left(self.data, [j, -1, -1])
        i = max(0, k-1)
        while i < len(self.data):
            if self.data[i][0] <= j < self.data[i][0] + self.data[i][2]:
                return i
            i += 1
    
    def flip(self, j):
        i = self._get(j)
        self.down_count(i)
        if self.data[i][0] < j < self.data[i][0] + self.data[i][2] - 1:
            hi = self.data[i][0] + self.data[i][2]
            self.data[i][2] = j - self.data[i][0]
            self.up_count(i)
            bisect.insort(self.data, [j, 1-self.data[i][1], 1])
            self.up_count(i+1)
            bisect.insort(self.data, [j+1, self.data[i][1], hi-j-1])
            self.up_count(i+2)
            return
        if self.data[i][2] == 1:
            self.data[i][1] = 1 - self.data[i][1]
            self.up_count(i)
            self.maybe_merge(i)
            self.maybe_merge(i-1)
            return
        if self.data[i][0] == j:
            acc, val, size = self.data[i]
            self.data[i] = [acc, 1 - val, 1]
            self.up_count(i)
            bisect.insort(self.data, [acc+1, val, size-1])
            self.up_count(i+1)
            self.maybe_merge(i-1)
            return
        acc, val, size = self.data[i]
        self.data[i] = [acc, val, size-1]
        self.up_count(i)
        bisect.insort(self.data, [acc+size-1, 1-val, 1])
        self.up_count(i+1)
        self.maybe_merge(i+1)
        return
    
    def maybe_merge(self, i):
        if i in (-1, len(self.data) - 1):
            return
        self.down_count(i)
        self.down_count(i+1)
        popped = self.data.pop(i+1)
        self.data[i][2] += popped[2]
        self.up_count(i)
    
    def count_groups(self, size):
        return self.group_counts[size]
    
    def up_count(self, i):
        lo, _, group = self.data[i]
        if lo >= self.length:
            return
        for size in self.sizes:
            if size > group:
                break
            self.group_counts[size] += min(group - size + 1, self.length - lo)
    
    def down_count(self, i):
        lo, _, group = self.data[i]
        if lo >= self.length:
            return
        for size in self.sizes:
            if size > group:
                break
            self.group_counts[size] -= min(group - size + 1, self.length - lo)
41800