<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 typing import List

from collections import defaultdict

class Solution:
	def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:
		result: List[int] = []

		size_map = defaultdict(int)

		alternating_groups: List[List[int]] = []

		def find_alternating_idx_group_by_color_idx(color_idx: int):
			if color_idx == 0:
				return 0
			# Binary search on alternating_groups
			low = 0
			high = len(alternating_groups) - 1
			while low <= high:
				mid = (low + high) // 2
				group = alternating_groups[mid]
				if group[0] <= color_idx < group[1]:
					return mid
				elif group[0] > color_idx:
					high = mid - 1
				else:
					low = mid + 1
			return -1


		def update_size_map(size_at: int, add = True):
			initial_size = size_at
			while size_at > 0:
				if add:
					size_map[size_at] += (initial_size - size_at) + 1
				else:
					size_map[size_at] -= (initial_size - size_at) + 1
				size_at -= 1

		def group_size(group: List[int]):
			return group[1] - group[0]

		idx = 0
		while idx < len(colors):
			last_color = None
			j = idx
			while j < len(colors) and last_color != colors[j]:
				last_color = colors[j]
				j += 1
			group = [idx, j]
			update_size_map(group_size(group))
			alternating_groups.append(group)
			idx = j

		def process_color_change(query: List[int]):
			_, index, color = query
			if colors[index] == color:
				return
			colors[index] = color
			assert alternating_groups
			# Find index of group which contains the index
			idx = find_alternating_idx_group_by_color_idx(index)
			main_group = alternating_groups[idx]
			assert main_group[0] <= index < main_group[1]
			# Possibles cases:
			#  - main group has a length of one -> merge with outside groups
			if main_group[1] - main_group[0] == 1:
				left_group = main_group if idx == 0 else alternating_groups[idx - 1]
				right_group = main_group if idx == len(alternating_groups) - 1 else alternating_groups[idx + 1]
				# Remove concerned groups from the group map
				new_group = [left_group[0], right_group[1]]
				update_size_map(group_size(main_group), False)
				update_size_map(group_size(left_group), False)
				update_size_map(group_size(right_group), False)
				update_size_map(group_size(new_group))
				if idx == 0:
					alternating_groups[0] = new_group
					if right_group is not main_group:
						alternating_groups.pop(1)
				else:
					if left_group is not main_group:
						alternating_groups[idx - 1] = new_group
						alternating_groups.pop(idx)
						if right_group is not main_group:
							alternating_groups.pop(idx)
					else:
						alternating_groups[0] = new_group
						if right_group is not main_group:
							alternating_groups.pop(1)
			#  - index is on left boundary -> merge with boundary group
			elif index == main_group[0] and idx != 0:
				prev_group = alternating_groups[idx - 1]
				update_size_map(group_size(main_group), False)
				update_size_map(group_size(prev_group), False)
				update_size_map(group_size(main_group) - 1)
				update_size_map(group_size(prev_group) + 1)
				alternating_groups[idx - 1] = [prev_group[0], index + 1]
				alternating_groups[idx] = [index + 1, main_group[1]]
			# - index is on right boundary -> grow next group
			elif index == main_group[1] - 1 and idx != len(alternating_groups) - 1:
				next_group = alternating_groups[idx + 1]
				update_size_map(group_size(main_group), False)
				update_size_map(group_size(next_group), False)
				update_size_map(group_size(main_group) - 1)
				update_size_map(group_size(next_group) + 1)
				alternating_groups[idx] = [main_group[0], index]
				alternating_groups[idx + 1] = [index, next_group[1]]
			#  - index is within group -> split group
			else:
				left_group = [main_group[0], index]
				middle_group = [index, index + 1]
				right_group = [index + 1, main_group[1]]
				if group_size(right_group) != 0:
					alternating_groups[idx] = right_group
					alternating_groups.insert(idx, middle_group)
				else:
					alternating_groups[idx] = middle_group
				if group_size(left_group) != 0:
					alternating_groups.insert(idx, left_group)
				update_size_map(group_size(main_group), False)
				update_size_map(group_size(left_group))
				update_size_map(group_size(middle_group))
				update_size_map(group_size(right_group))

		def process_query(query: List[int]):
			_, size = query
			if len(alternating_groups) == 1 and colors[0] != colors[-1]:
				# Edge case whole array of colors is switching
				return len(colors)
			amnt = size_map[size]
			# Check if we can combine the end and start
			if colors[0] != colors[-1]:
				first_group, last_group = alternating_groups[0], alternating_groups[-1]
				group_len_1, group_len_2 = first_group[1] - first_group[0], last_group[1] - last_group[0]
				if group_len_1 + group_len_2 >= size:
					if group_len_1 >= size:
						amnt -= group_len_1 - size + 1
					if group_len_2 >= size:
						amnt -= group_len_2 - size + 1
					amnt += (group_len_1 + group_len_2) - size + 1
			return amnt


		skip_next = False
		for idx, query in enumerate(queries):
			# Special case when we have two queries that will cancel each other
			# We do this because our update complexity is suboptimal
			if skip_next:
				skip_next = False
				continue
			if idx != len(queries) - 1 and query[0] == 2 and queries[idx + 1][0] == 2:
				next_query = queries[idx + 1]
				if next_query[1] == query[1] and next_query[2] != query[2]:
					if colors[query[1]] != query[2]:
						skip_next = True
						continue
			if query[0] == 2:
				process_color_change(query)
			elif query[0] == 1:
				result.append(process_query(query))
		return result

43800