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

import bisect


class Solver:
    def __init__(self, colors: list[int], queries: list[list[int]]) -> None:
        self.colors = colors
        self.queries = queries
        self.length = len(colors)
        self.sequences: list[tuple[int, int]] = []
        self.sizes: list[tuple[int, int]] = []

    def map_colors(self) -> None:
        first_start = self.first_sequence_start()
        if first_start == -1:
            return

        first_end = -1
        first = True
        pi = first_start
        prev = self.colors[first_start]
        for i in range(first_start + 1, first_start + self.length + 1):
            ri = self.fix_index(i)
            if self.colors[ri] == prev:
                if not first or first_start == 0:
                    seq = (pi, ri)
                    self.sequences.append(seq)
                    self.change_size(self.length_sequence(seq), 1)

                if first:
                    first_end = ri
                    first = False

                pi = ri

            prev = self.colors[ri]

        if first_start > 0:
            seq = (first_start, first_end)
            self.sequences.append(seq)
            self.change_size(self.length_sequence(seq), 1)

    def change_size(self, size: int, delta: int) -> None:
        i = self.size_index(size)
        if i == len(self.sizes) or self.sizes[i][0] != size:
            self.set_size_at_index(size, delta, i)
            return

        (_, v) = self.sizes[i]
        nv = v + delta
        if nv == 0:
            self.sizes.pop(i)
        else:
            self.sizes[i] = (size, nv)

    def set_size(self, size: int, value: int) -> None:
        i = self.size_index(size)
        if value == 0:
            if self.sizes:
                self.sizes.pop(i)
        else:
            self.set_size_at_index(size, value, i)

    def set_size_at_index(self, size: int, value: int, i: int) -> None:
        if i == len(self.sizes):
            self.sizes.append((size, value))
        elif self.sizes[i][0] == size:
            self.sizes[i] = (size, value)
        else:
            self.sizes = self.sizes[:i] + [(size, value)] + self.sizes[i:]

    def size_index(self, size: int) -> int:
        return bisect.bisect_left(self.sizes, size, key=lambda e: e[0])

    def first_sequence_start(self) -> int:
        prev = self.colors[0]
        pi = 0
        for i in reversed(range(0, self.length)):
            if self.colors[i] == prev:
                return pi

            prev = self.colors[i]
            pi = i

        return -1

    def solve(self) -> list[int]:
        result = []

        self.map_colors()

        for q in self.queries:
            total = 0
            if q[0] == 1:
                if self.sequences:
                    size = q[1]
                    start = self.size_index(size)
                    for i in range(start, len(self.sizes)):
                        (s, v) = self.sizes[i]
                        total += v * (s - q[1] + 1)

                    result.append(total)
                elif self.length == q[1]:
                    result.append(1)
                else:
                    result.append(self.length)

            else:
                self.change(q[1], q[2])

        return result

    def sequence_index(self, i: int) -> int:
        if len(self.sequences) == 1:
            return 0

        si = bisect.bisect_left(self.sequences, i, key=lambda e: e[0])

        if si == len(self.sequences):
            return si - 1

        if self.sequences[si][0] == i:
            return si

        if si == 0:
            return len(self.sequences) - 1

        return si - 1

    def next_index(self, i: int) -> int:
        return 0 if i == len(self.sequences) - 1 else i + 1

    def prev_index(self, i: int) -> int:
        return len(self.sequences) - 1 if i == 0 else i - 1

    def fix_index(self, i: int) -> int:
        return i % self.length

    def length_sequence(self, seq: tuple[int, int]) -> int:
        if seq[0] == seq[1]:
            return self.length

        if seq[0] > seq[1]:
            return self.length + seq[1] - seq[0]

        return seq[1] - seq[0]

    def change(self, i: int, c: int) -> None:
        if self.colors[i] == c:
            return

        self.colors[i] = c

        if not self.sequences:
            self.change_full_circle(i)
            return

        si = self.sequence_index(i)
        seq = self.sequences[si]
        if self.length_sequence(seq) == 1:
            self.change_length_one(si)
        elif i == seq[0]:
            self.change_first_in_sequence(i, si, seq)
        elif i == self.fix_index(seq[1] - 1):
            self.change_last_in_sequence(i, si, seq)
        else:
            self.change_middle_of_sequence(i, si, seq)

    def change_full_circle(self, i: int) -> None:
        ni = self.fix_index(i + 1)
        self.sequences = [(i, ni), (ni, i)] if i < ni else [(ni, i), (i, ni)]
        self.set_size(self.length, 0)
        self.set_size(1, 1)
        self.set_size(self.length - 1, 1)

    def change_length_one(self, si: int) -> None:
        pi = self.prev_index(si)
        prev = self.sequences[pi]
        if len(self.sequences) == 2:
            self.sequences = []
            self.sizes = []
        else:
            ni = self.next_index(si)
            nxt = self.sequences[ni]
            self.sequences[pi] = (prev[0], nxt[1])
            (remove1, remove2) = (ni, si) if si < ni else (si, ni)
            self.sequences.pop(remove1)
            self.sequences.pop(remove2)
            prevl = self.length_sequence(prev)
            nxtl = self.length_sequence(nxt)
            self.change_size(prevl, -1)
            self.change_size(1, -1)
            self.change_size(nxtl, -1)
            self.change_size(prevl + 1 + nxtl, 1)

    def change_first_in_sequence(self, i: int, si: int, seq: tuple[int, int]) -> None:
        if len(self.sequences) == 1:
            ni = self.fix_index(i + 1)
            self.sequences = [(ni, ni)]
            return

        pi = self.prev_index(si)
        prev = self.sequences[pi]
        fi = self.fix_index(i + 1)
        self.sequences[pi] = (prev[0], fi)
        if fi == 0:
            self.sequences.pop()
            self.sequences = [(fi, seq[1])] + self.sequences
        else:
            self.sequences[si] = (fi, seq[1])
        prevl = self.length_sequence(prev)
        seql = self.length_sequence(seq)
        self.change_size(prevl, -1)
        self.change_size(seql, -1)
        self.change_size(prevl + 1, 1)
        self.change_size(seql - 1, 1)

    def change_last_in_sequence(self, i: int, si: int, seq: tuple[int, int]) -> None:
        if len(self.sequences) == 1:
            self.sequences = [(i, i)]
            return

        ni = self.next_index(si)
        nxt = self.sequences[ni]
        if i == self.length - 1:
            self.sequences = self.sequences[1:-1] + [(seq[0], i), (i, nxt[1])]
        else:
            self.sequences[si] = (seq[0], i)
            self.sequences[ni] = (i, nxt[1])
        seql = self.length_sequence(seq)
        nxtl = self.length_sequence(nxt)
        self.change_size(seql, -1)
        self.change_size(nxtl, -1)
        self.change_size(seql - 1, 1)
        self.change_size(nxtl + 1, 1)

    def change_middle_of_sequence(self, i: int, si: int, seq: tuple[int, int]) -> None:
        ip1 = self.fix_index(i + 1)

        ns1 = (seq[0], i)
        ns2 = (i, ip1)
        ns3 = (ip1, seq[1])

        if i < self.sequences[0][0]:
            self.sequences = [ns2, ns3] + self.sequences[:si] + [ns1]
        elif ip1 < self.sequences[0][0]:
            self.sequences = [ns3] + self.sequences[:si] + [ns1, ns2]
        else:
            self.sequences = self.sequences[:si] + [ns1, ns2, ns3] + self.sequences[(si + 1) :]

        self.change_size(self.length_sequence(seq), -1)
        self.change_size(self.length_sequence(ns1), 1)
        self.change_size(1, 1)
        self.change_size(self.length_sequence(ns3), 1)


class Solution:
    def numberOfAlternatingGroups(self, colors: list[int], queries: list[list[int]]) -> list[int]:
        return Solver(colors, queries).solve()

39900