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


"""     VERY VERY VERY VERY VERY VERY VERY VERY VERY VERY  DIFFICULT    """
"""     VERY VERY VERY VERY VERY VERY VERY VERY VERY VERY  DIFFICULT    """
"""     VERY VERY VERY VERY VERY VERY VERY VERY VERY VERY  DIFFICULT    """

# IMPLEMENTATION OF THIS CODE IS HUGE AND VERY COMPLICATED BUT U WILL GET IT
# CRAZYYYYYYYYYYY ULTRA PRO MAX ( :) :) :) :) :) :) :) :) :) :) :) :) :) :) )

# OVER ALL Time Complexity is O( n log n )   - USED Segment Tree 
# Updating Segment Tree and also BINARY SEARCH on SORTEDLIST
# Try to Implement By just understanding once and Implement It 


from sortedcontainers import SortedList
import bisect

class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.tree_val = [0] * (4 * n)
        self.tree_cnt = [0] * (4 * n)

    def query_sum(self, x):
        return self._query_sum(x, self.n - 1, 0, self.n - 1, 0)

    def query_cnt(self, x):
        return self._query_cnt(x, self.n - 1, 0, self.n - 1, 0)

    def update(self, ind, val):
        self._update(ind, val, 0, self.n - 1, 0)

    def _query_sum(self, x, y, l, r, i):
        if r < x or l > y:
            return 0
        if l >= x and r <= y:
            return self.tree_val[i]

        m = (l + r) // 2
        return self._query_sum(x, y, l, m, i * 2 + 1) + self._query_sum(x, y, m + 1, r, i * 2 + 2)

    def _query_cnt(self, x, y, l, r, i):
        if r < x or l > y:
            return 0
        if l >= x and r <= y:
            return self.tree_cnt[i]

        m = (l + r) // 2
        return self._query_cnt(x, y, l, m, i * 2 + 1) + self._query_cnt(x, y, m + 1, r, i * 2 + 2)

    def _update(self, ind, val, l, r, i):
        if l == r:
            self.tree_cnt[i] += val
            self.tree_val[i] = self.tree_cnt[i] * l
            return

        m = (l + r) // 2
        if m >= ind:
            self._update(ind, val, l, m, i * 2 + 1)
        else:
            self._update(ind, val, m + 1, r, i * 2 + 2)

        self.tree_val[i] = self.tree_val[i * 2 + 1] + self.tree_val[i * 2 + 2]
        self.tree_cnt[i] = self.tree_cnt[i * 2 + 1] + self.tree_cnt[i * 2 + 2]


class Solution:
    def __init__(self):
        self.n = 0

    def count(self, q, last, tree):
        sum_val = tree.query_sum(q)
        cnt = tree.query_cnt(q)
        ans = sum_val - (q - 1) * cnt

        l, r = last
        if l >= self.n or (r - l + 1) < q:
            return ans

        if r >= self.n:
            can = self.n - l
            has = (r - l + 1) - (q - 1)
            if can < has:
                ans -= (has - can)
        return ans

    def remove(self, val, all_set, tree):
        all_set.remove(val)
        if val[0] >= self.n:
            return

        tree.update(val[1] - val[0] + 1, -1)

    def insert(self, val, all_set, tree):
        all_set.add(val)
        if val[0] >= self.n:
            return

        tree.update(val[1] - val[0] + 1, 1)

    def group_containing_x(self, ind, all_set):
        pos = bisect.bisect_right(all_set, (ind, -1))
        if pos > 0 and all_set[pos - 1][1] >= ind:
            return all_set[pos - 1]
        return all_set[pos] if pos < len(all_set) else (float('inf'), float('inf'))

    def update(self, ind, val, all_set, arr, tree):
        if ind == 2 * self.n - 1 or arr[ind] == val:
            return
        arr[ind] = val

        with_ind = self.group_containing_x(ind, all_set)
        self.remove(with_ind, all_set, tree)
        l, r = with_ind

        if l < ind < r:
            self.insert((l, ind - 1), all_set, tree)
            self.insert((ind, ind), all_set, tree)
            self.insert((ind + 1, r), all_set, tree)
            return

        if l == ind and r != ind:
            self.insert((l + 1, r), all_set, tree)
        if r == ind and l != ind:
            self.insert((l, r - 1), all_set, tree)

        l = r = ind
        to_remove = []

        pos = bisect.bisect_right(all_set, (ind, -1))

        lft_pos = pos - 1
        while lft_pos >= 0 and arr[all_set[lft_pos][1]] != arr[l]:
            to_remove.append(all_set[lft_pos])
            l = all_set[lft_pos][0]
            lft_pos -= 1

        rgt_pos = pos
        while rgt_pos < len(all_set) and arr[all_set[rgt_pos][0]] != arr[r]:
            to_remove.append(all_set[rgt_pos])
            r = all_set[rgt_pos][1]
            rgt_pos += 1

        for item in to_remove:
            self.remove(item, all_set, tree)
        self.insert((l, r), all_set, tree)

    def numberOfAlternatingGroups(self, colors, queries):
        self.n = len(colors)

        arr = colors + colors

        tree = SegmentTree(2 * self.n)

        all_set = SortedList()
        j = 0
        while j < 2 * self.n - 1:
            l, r = j, j + 1
            while r < 2 * self.n - 1 and arr[r] != arr[r - 1]:
                r += 1

            self.insert((l, r - 1), all_set, tree)
            j = r

        result = []
        for q in queries:
            if q[0] == 1:
                result.append(self.count(q[1], self.group_containing_x(self.n, all_set), tree))
            else:
                ind, val = q[1], q[2]
                self.update(ind, val, all_set, arr, tree)
                self.update(self.n + ind, val, all_set, arr, tree)

        return result

45200