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

from sortedcontainers import SortedList

class Solution:
    def __init__(self):
        self.alt = []
        self.ct = []
        self.seg = []
        self.st = SortedList()
        self.n = 0

    def findGroup(self, index):
        pos = self.st.bisect_right((index, float('inf')))
        
        if pos == 0:
            return (-1, -1)
        
        it = self.st[pos - 1]
        
        if it[0] <= index <= it[0] + it[1] - 1:
            return it
        else:
            return (-1, -1)

    def update(self, index, val):
        idx = index + self.n + 1
        self.seg[idx] += val * (index + 2)
        self.ct[idx] += val
        
        while idx > 1:
            idx //= 2
            self.seg[idx] = self.seg[2 * idx] + self.seg[2 * idx + 1]
            self.ct[idx] = self.ct[2 * idx] + self.ct[2 * idx + 1]

    def query(self, l, r):
        r += 1
        x, y = 0, 0
        l += self.n + 1
        r += self.n + 1
        
        while l < r:
            if l & 1:
                x += self.seg[l]
                y += self.ct[l]
                l += 1
            if r & 1:
                r -= 1
                x += self.seg[r]
                y += self.ct[r]
            l //= 2
            r //= 2
        
        return (x, y)

    def flip(self, index):
        self.alt[index] = 1 - self.alt[index]
        if self.alt[index] == 1:
            g1 = self.findGroup(index - 1)
            g2 = self.findGroup(index + 1)
            x = (-1, -1)
            if g1 == x:
                if g2 == x:
                    self.st.add((index, 1))
                    self.update(1, -1)
                else:
                    self.st.remove(g2)
                    self.update(g2[1], -1)
                    self.st.add((index, g2[1] + 1))
                    self.update(g2[1] + 1, 1)
            else:
                if g2 == x:
                    self.st.remove(g1)
                    self.update(g1[1], -1)
                    self.st.add((g1[0], g1[1] + 1))
                    self.update(g1[1] + 1, 1)
                else:
                    self.st.remove(g1)
                    self.st.remove(g2)
                    self.update(g1[1], -1)
                    self.update(g2[1], -1)
                    self.st.add((g1[0], g1[1] + g2[1] + 1))
                    self.update(g1[1] + g2[1] + 1, 1)
        else:
            g = self.findGroup(index)
            self.st.remove(g)
            self.update(g[1], -1)
            if g[1] != 1:
                if g[0] < index:
                    self.st.add((g[0], index - g[0]))
                    self.update(index - g[0], 1)
                if g[0] + g[1] - 1 > index:
                    self.st.add((index + 1, g[0] + g[1] - (index + 1)))
                    self.update(g[0] + g[1] - (index + 1), 1)

    def altGroups(self, val):
        if len(self.st) == 1 and self.st[0][1] == self.n:
            return self.n
        
        ret = self.query(val - 1, self.n)
        ans = ret[0] - (ret[1] * val)

        if len(self.st) >= 2 and self.alt[0] == 1 and self.alt[self.n - 1] == 1:
            g1 = self.st[0]
            g2 = self.st[-1]
            if g1[1] >= val - 1:
                ans -= g1[1] - val + 2
            if g2[1] >= val - 1:
                ans -= g2[1] - val + 2
            if g1[1] + g2[1] >= val - 1:
                ans += g1[1] + g2[1] - val + 2
        
        return ans

    def numberOfAlternatingGroups(self, colors, queries):
        self.n = len(colors)
        self.ct = [0] * (4 * self.n)
        self.seg = [0] *  (4 * self.n)
        self.alt = [colors[i] != colors[(i + 1) % self.n] for i in range(self.n)]
        
        i = 0
        while i < self.n:
            if self.alt[i] == 0:
                i += 1
                continue
            j = i
            while j < self.n and self.alt[j] == 1:
                j += 1
            self.st.add((i, j - i))
            self.update(j - i, 1)
            i = j

        ans = []
        for q in queries:
            if len(q) == 2:
                ans.append(self.altGroups(q[1]))
            else:
                if colors[q[1]] == q[2]:
                    continue
                colors[q[1]] = q[2]
                self.flip(q[1])
                self.flip((q[1] - 1 + self.n) % self.n)
        
        return ans

41100