<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 BIT:
    def __init__(self, size):
        self.N = size + 10
        self.t1 = [0] * self.N
        self.t2 = [0] * self.N

    def lowbit(self, x):
        return x & -x

    def update(self, k, val):
        i = k
        while i < self.N:
            self.t1[i] += val
            self.t2[i] += k * val
            i += self.lowbit(i)

    def ask(self, k):
        ans = 0
        i = k
        while i > 0:
            ans += (k + 1) * self.t1[i] - self.t2[i]
            i -= self.lowbit(i)
        return ans

class OrderedMap:
    def __init__(self):
        self.keys = []
        self.map = {}

    def insert(self, key, value):
        from bisect import bisect_left, insort_left
        if key not in self.map:
            insort_left(self.keys, key)
        self.map[key] = value

    def remove(self, key):
        from bisect import bisect_left
        if key in self.map:
            idx = bisect_left(self.keys, key)
            self.keys.pop(idx)
            del self.map[key]

    def find(self, key):
        from bisect import bisect_left
        idx = bisect_left(self.keys, key)
        if idx == len(self.keys):
            idx = 0  # Circular behavior
        return self.keys[idx], self.map[self.keys[idx]]

    def empty(self):
        return not self.keys

    def size(self):
        return len(self.keys)

    def begin(self):
        key = self.keys[0]
        return key, self.map[key]

class Solution:
    def numberOfAlternatingGroups(self, colors, queries):
        n = len(colors)
        a = colors
        st = OrderedMap()
        l = 0

        # Preprocessing 1: Obtain the alternating groups
        while l < n:
            r = l + 1
            while (r - l + 1 <= n) and (a[r % n] != a[(r - 1) % n]):
                r += 1
            st.insert((r - 1) % n, l)
            l = r

        # Helper functions
        def find(i):
            r, l = st.find(i)
            return r, l

        def length(l, r):
            if r < l:
                return r + n - l + 1
            else:
                return r - l + 1

        def check():
            if st.size() == 1:
                r, l = st.begin()
                return a[r] != a[l]
            return False

        def del_interval(i):
            r, l = find(i)
            st.remove(r)
            bit.update(n + 1 - length(l, r), -1)
            return r, l

        def add_interval(l, r):
            st.insert(r, l)
            bit.update(n + 1 - length(l, r), 1)

        # Preprocessing 2: Initialize the Fenwick Tree
        T = n
        bit = BIT(n + 10)
        for r in st.keys:
            l = st.map[r]
            bit.update(n + 1 - length(l, r), 1)

        ans = []
        for e in queries:
            if e[0] == 2:
                i = e[1]
                val = e[2]
                if a[i] == val:
                    continue
                a[i] = val
                r, l = del_interval(i)
                if l == r:
                    u = (i - 1 + n) % n
                    v = (i + 1) % n
                    if u != i and a[u] != a[i] and not st.empty():
                        l = del_interval(u)[1]
                    if v != i and a[v] != a[i] and not st.empty():
                        r = del_interval(v)[0]
                    add_interval(l, r)
                elif i == l:
                    add_interval((i + 1) % n, r)
                    u = (i - 1 + n) % n
                    if u != i and a[u] != a[i] and not st.empty():
                        l = del_interval(u)[1]
                    add_interval(l, i)
                elif i == r:
                    add_interval(l, (i - 1 + n) % n)
                    v = (i + 1) % n
                    if v != i and a[v] != a[i] and not st.empty():
                        r = del_interval(v)[0]
                    add_interval(i, r)
                else:
                    u = (i - 1 + n) % n
                    v = (i + 1) % n
                    if length(l, r) == n and a[l] != a[r]:
                        add_interval(v, u)
                    else:
                        add_interval(l, u)
                        add_interval(v, r)
                    add_interval(i, i)
            else:
                if check():
                    ans.append(n)
                else:
                    ans.append(bit.ask(n + 1 - e[1]))
        return ans

41000