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


l = [0] + [i & -i for i in range(1, 50001)]

class F:
    def __init__(self, n):
        self.a = [0] * (n + 1)
    
    def add(self, i, v):
        while i < len(self.a):
            self.a[i] += v
            i += l[i]
    
    def query(self, i, j):
        return 0 if i > j else self._query(j) - self._query(i - 1)

    def _query(self, i):
        ret = 0
        while i > 0:
            ret += self.a[i]
            i -= l[i]
        return ret
    
class FF:
    def __init__(self, n):
        self.a = F(n)
        self.b = F(n)
    
    def add(self, i, v):
        self.a.add(i, v * i)
        self.b.add(i, v)

    def query(self, i, j):
        ret = self.a.query(i, j)
        if i != 1:
            ret -= self.b.query(i, j) * (i - 1)
        return ret


class Node:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.m = (l + r) // 2
        self.size = r - l + 1
        self.lson = self.rson = None
        self.p = self.q = 0

class Tree:
    def __init__(self, a):
        self.a = a
        self.n = len(a)
        self.ff = FF(self.n)
        self.full = False

        self.cache = Counter()
        self.root = self.build(0, self.n - 1)
        self.apply()

    def apply(self):
        for k, v in self.cache.items():
            if v != 0:
                self.ff.add(k, v)

    def maintain(self, node, diff):
        if self.a[node.lson.r] != self.a[node.rson.l]:
            if node.lson.q != node.lson.size and node.rson.p != node.rson.size:
                self.cache[node.lson.q + node.rson.p] += diff
        else:
            if node.lson.q != node.lson.size:
                self.cache[node.lson.q] += diff
            if node.rson.p != node.rson.size:
                self.cache[node.rson.p] += diff

        if (node.l, node.r) == (0, self.n - 1):
            self.full = False
            if self.a[0] != self.a[-1]:
                self.full = diff == 1 and node.p + node.q >= self.n
                self.cache[min(node.p + node.q, self.n)] += diff
            else:
                self.cache[node.p] += diff
                if node.p != self.n:
                    self.cache[node.q] += diff

    def query(self, i):
        return self.ff.query(i, self.n)

    def build(self, l, r):
        node = Node(l, r)
        if node.size == 1:
            node.p = node.q = 1
        else:
            node.lson = self.build(l, node.m)
            node.rson = self.build(node.m + 1, r)
            node.p = node.lson.p if (node.lson.p < node.lson.size or self.a[node.lson.r] == self.a[node.rson.l]) else node.lson.size + node.rson.p
            node.q = node.rson.q if (node.rson.q < node.rson.size or self.a[node.lson.r] == self.a[node.rson.l]) else node.rson.size + node.lson.q
            self.maintain(node, 1)

        return node
    
    def change(self, i, v):
        if self.a[i] != v:
            self.cache = Counter()
            self._change(self.root, i, v)
            self.apply()
    
    def _change(self, node, i, v):
        if node.size == 1:
            self.a[i] = v
        else:
            self.maintain(node, -1)
            self._change(node.lson if i <= node.m else node.rson, i, v)
            node.p = node.lson.p if (node.lson.p < node.lson.size or self.a[node.lson.r] == self.a[node.rson.l]) else node.lson.size + node.rson.p
            node.q = node.rson.q if (node.rson.q < node.rson.size or self.a[node.lson.r] == self.a[node.rson.l]) else node.rson.size + node.lson.q
            self.maintain(node, 1)


class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        tree = Tree(colors)
        ans = []
        # print(tree.a, tree.full)
        for query in queries:
            if query[0] == 1:
                ans.append(tree.n if tree.full and tree.n % 2 == 0 else tree.query(query[1]))
            else:
                tree.change(query[1], query[2])
                # print(tree.a, tree.full)
        
        return ans

48300