<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 Solution:
    def numberOfAlternatingGroups(
        self, colors: List[int], queries: List[List[int]]
    ) -> List[int]:
        N = len(colors)
        badi = []
        for i in range(N):
            if colors[i] == colors[(i + 1) % N]:
                badi.append(i)

        def calsize(left, right):
            size = (right - left + N) % N
            if size == 0:
                size = N
            return size


        def regenerate_sizes():
            if not badi:
                sizes[:] = [N]
            else:
                sizes[:] = sorted([calsize(badi[i], badi[(i + 1) % len(badi)]) for i in range(len(badi))])

        # print(badi)
        sizes = []
        regenerate_sizes()
        # print(sizes)

        def addsize(size):
            lo = 0
            hi = len(sizes)
            while lo < hi:
                mid = (lo + hi) // 2
                if sizes[mid] < size:
                    lo = mid + 1
                else:
                    hi = mid
            assert len(sizes) == lo or sizes[lo] >= size
            sizes.insert(lo, size)

        def removesize(size):
            lo = 0
            hi = len(sizes)
            while lo < hi:
                mid = (lo + hi) // 2
                if sizes[mid] < size:
                    lo = mid + 1
                else:
                    hi = mid
            assert sizes[lo] == size
            sizes.pop(lo)

        def addbad(index):
            # print(index, badi, sizes)
            lo = 0
            hi = len(badi)
            while lo < hi:
                mid = (lo + hi) // 2
                if badi[mid] < index:
                    lo = mid + 1
                else:
                    hi = mid

            badi.insert(lo, index)

            if len(badi) < 5:
                regenerate_sizes()
            else:
                m = len(badi)
                left = badi[(lo + m - 1) % m]
                right = badi[(lo + 1) % m]

                removesize(calsize(left, right))
                addsize(calsize(left, index))
                addsize(calsize(index, right))

            # print(index, badi, sizes)

        def removebad(index):
            # print(index, badi, sizes)
            lo = 0
            hi = len(badi)
            while lo < hi:
                mid = (lo + hi) // 2
                if badi[mid] < index:
                    lo = mid + 1
                else:
                    hi = mid
            assert badi[lo] == index

            m = len(badi)
            left = badi[(lo + m - 1) % m]
            right = badi[(lo + 1) % m]

            badi.pop(lo)

            if len(badi) < 5:
                regenerate_sizes()
            else:
                removesize(calsize(left, index))
                removesize(calsize(index, right))
                addsize(calsize(left, right))

        def dochange(index, color):
            if colors[index] == color:
                return

            left = (index + N - 1) % N
            if colors[left] == colors[index]:
                # print("tt101a", left)
                removebad(left)
            else:
                # print("tt101b", left)
                addbad(left)

            # print(badi, sizes)

            right = (index + 1) % N
            if colors[index] == colors[right]:
                # print("tt102a", index)
                removebad(index)
            else:
                # print("tt102b", index)
                addbad(index)

            colors[index] = color


        def helper(target):
            lo = 0
            hi = len(sizes)
            while lo < hi:
                mid = (lo + hi) // 2
                if target > sizes[mid]:
                    lo = mid + 1
                else:
                    hi = mid
            
            ans = 0
            for i in range(lo, len(sizes)):
                ans += sizes[i] - target + 1
            return ans


        ans = []
        for query in queries:
            if query[0] == 1:
                size = query[1]

                if sizes == [N] and N % 2 == 0:
                    ans.append(N)
                else:
                    ans.append(helper(size))


            else:
                # print(badi, sizes)
                dochange(query[1], query[2])
                # print(badi, sizes)

        return ans

        
39300