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

        # # SLIDING WINDOW - TLE
        # ans, n = [], len(colors)
        # for q in queries:
        #     if q[0] == 2:
        #         colors[q[1]] = q[2]
        #     else:
        #         seq, prev, k, cnt = 0, colors[0], q[1], 0
        #         for i in range(n + k - 1):
        #             if colors[i % n] != prev:
        #                 dist += 1
        #                 if dist >= k:
        #                     cnt += 1
        #             else:
        #                 dist = 1
        #             prev = colors[i % n]
        #         ans.append(cnt)
        # return ans

        # SEGMENT TREE + SORTED LIST
        from sortedcontainers import SortedList
        n = len(colors) # 1-long seq freq at 0 index and so on
        # fill intervals
        intervals, seq_len = SortedList(), 0
        for idx in range(1, n + n):
            actual_idx = idx % n
            if colors[idx % n] == colors[(idx - 1) % n]:
                intervals.add((idx - seq_len - 1, idx - 1))
                seq_len = 0
            else:
                seq_len += 1
        intervals.add((n + n - seq_len - 1, n + n - 1))
        # count frequencies
        freq = [0] * n
        for start, end in intervals:
            if end >= n:
                break
            freq[end - start] += 1
        # traverse queries
        ans, tree = [], SegmentTree(len(freq), freq)
        for q in queries:
            if q[0] == 2: # update query
                if colors[q[1]] == q[2]: # no changes
                    continue
                colors[q[1]] = q[2]
                for idx in (q[1] + n, q[1]):
                    intervals_pos = intervals.bisect_right((idx, n + n)) - 1
                    start, end = intervals[intervals_pos]
                    if start == end: # merge left and right and middle
                        if end < n:
                            tree.update(0, -1)
                        if intervals_pos != len(intervals) - 1:
                            next_start, next_end = intervals[intervals_pos + 1]
                            if next_end < n:
                                tree.update(next_end - next_start, -1)
                            end = next_end
                            intervals.pop(intervals_pos + 1)
                        if intervals_pos != 0:
                            prev_start, prev_end = intervals[intervals_pos - 1]
                            if prev_end < n:
                                tree.update(prev_end - prev_start, -1)
                            start = prev_start
                            intervals.pop(intervals_pos)
                            intervals_pos -=  1
                        intervals.pop(intervals_pos)
                        intervals.add((start, end))
                        if end < n:
                            tree.update(end - start, 1)
                    elif start == idx:
                        if intervals_pos > 0:
                            prev_start, prev_end = intervals[intervals_pos - 1]
                            if prev_end < n:
                                tree.update(prev_end - prev_start, -1)
                            if idx < n:
                                tree.update(idx - prev_start, 1)
                            intervals.pop(intervals_pos - 1)
                            intervals.add((prev_start, idx))
                        else:
                            intervals.add((start, start))
                            tree.update(0, 1)
                            intervals_pos += 1
                        intervals.pop(intervals_pos)
                        intervals.add((start + 1, end))
                        if end < n:
                            tree.update(end - start, -1)
                            tree.update(end - start - 1, 1)
                    elif end == idx:
                        if intervals_pos != len(intervals) - 1:
                            next_start, next_end = intervals[intervals_pos + 1]
                            if next_end < n:
                                tree.update(next_end - next_start, -1)
                                tree.update(next_end - end, 1)
                            intervals.pop(intervals_pos + 1)
                            intervals.add((end, next_end))
                        else:
                            intervals.add((end, end))
                            tree.update(0, 1)
                        intervals.pop(intervals_pos)
                        intervals.add((start, end - 1))
                        if end < n:
                            tree.update(end - start, -1)
                        if end - 1 < n:                            
                            tree.update(end - 1 - start, 1)
                    else: 
                        intervals.pop(intervals_pos)
                        intervals.add((start, idx - 1))
                        intervals.add((idx, idx))
                        intervals.add((idx + 1, end))
                        if end < n:
                            tree.update(end - start, -1)
                            tree.update(end - idx - 1, 1)
                        if idx < n:
                            tree.update(0, 1)
                        if idx - 1 < n:
                            tree.update(idx - 1 - start, 1)
            else: # retrieve query
                cnt, total_sum = tree.query_range(q[1] - 1, n + n - 1)
                start, end = intervals[intervals.bisect_right((n, n + n)) - 1]
                extra = 0
                if end - start + 1 >= q[1]:
                    extra = min(end - start + 2 - q[1], n - start)
                ans.append(extra + total_sum - cnt * (q[1] - 1))
        return ans

class SegmentTree:
    
    def __init__(self, n: int, arr: List[int]):
        self.shift = (1 << (n - 1).bit_length()) - 1
        self.tree_cnt = [0] * (n + self.shift)
        self.tree_sum = [0] * (n + self.shift)
        if not arr: # fill with zeros
            return 
        # fill tree with provided values
        for i in range(n):
            self.tree_cnt[-i - 1] = arr[-i - 1]
            self.tree_sum[-i - 1] = arr[-i - 1] * (n - i)
        for i in reversed(range(self.shift)):
            for child_idx in (1 + i + i, 2 + i + i):
                if child_idx < len(self.tree_sum):
                    self.tree_sum[i] += self.tree_sum[child_idx]
                    self.tree_cnt[i] += self.tree_cnt[child_idx]
    
    def update(self, idx, delta_cnt):
        if delta_cnt == 0: # value has not changed
            return
        delta_sum = delta_cnt * (idx + 1)
        map_idx = self.shift + idx
        # update leaf node and all its parents
        while map_idx > 0:
            self.tree_cnt[map_idx] += delta_cnt
            self.tree_sum[map_idx] += delta_sum
            map_idx = (map_idx - 1) >> 1
        self.tree_cnt[map_idx] += delta_cnt
        self.tree_sum[map_idx] += delta_sum

    def __query_range(self, start, end, idx, left, right):
        if left > end or right < start: # out of range
            return (0, 0) # (cnt, sum)
        elif left >= start and right <= end: # fully inside range
            return (self.tree_cnt[idx], self.tree_sum[idx])
        # partially intersects
        mid = (left + right) >> 1
        cnt1, sum1 = self.__query_range(start, end, idx + idx + 1, left, mid)
        cnt2, sum2 = self.__query_range(start, end, idx + idx + 2, mid + 1, right)
        return (cnt1 + cnt2, sum1 + sum2)

    def query_range(self, start, end):
        return self.__query_range(start, end, 0, 0, self.shift)
42900