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

'''
Treap + segment-merge: O(nlogn). extremely long and error-prone.
1. extract alternating groups (i.e. segments) from the colors ring.
2. represent each segment (start, end) in 3 data structures:
  a. map: start -> end
  b. sortedlist: list of segment start, sorted.
  c. treap: the sizes of all segments. In each node, also store the subtree size and subtree sum.
3. for a count query, find the sum and count of all segment sizes >= target_size. result = sum - (target_size-1)*cnt
  the sum and cnt can be done in log(n) time using the treap
4. for an update query colors[p] <- c, find the segment that contains p, and update it (as well as its neighbor segments):
  a. if the segment is a single position at p, then the 2 neighbor segs can be merged
  b. if p is at the start or end of a segment, decrease the segment by 1, and increase the adjacent segment by 1
  c. if p is in the middle of a segment, break it up
  d. need to handle the case where the whole ring is a loop separately.

Edge cases:
1. only one segment, which is also a loop
2. when breaking a segment and trying to merge with its neighbor segments, there could be only 1 segment, 2 segments, or >= 3.
'''

import random 
from sortedcontainers import SortedList

# treap implementation: adapted from https://www.geeksforgeeks.org/implementation-of-search-insert-and-delete-in-treap/
# A Treap Node
class TreapNode:
    def __init__(self, key):
        self.key = key
        self.priority = random.randint(0, 100000)
        self.left = None
        self.right = None
        self.sum = key
        self.size = 1
# T1, T2 and T3 are subtrees of the tree rooted with y
#  (on left side) or x (on right side)
#                y                               x
#               / \     Right Rotation          /  \
#              x   T3   – – – – – – – >        T1   y
#             / \       < - - - - - - -            / \
#            T1  T2     Left Rotation            T2  T3 */
 
# A utility function to right rotate subtree rooted with y
# See the diagram given above.

def update_sum(root): # added function to keep track of subtree sum and subtree size
    if not root:
        return
    root.sum = (0 if not root.left else root.left.sum) + (0 if not root.right else root.right.sum) + root.key
    root.size = (0 if not root.left else root.left.size) + (0 if not root.right else root.right.size) + 1

def rightRotate(y):
    x = y.left
    T2 = x.right
    
    # Perform rotation
    x.right = y
    y.left = T2
    
    update_sum(y)
    update_sum(x)
     
    # Return new root
    return x
     
def leftRotate(x):
    y = x.right
    T2 = y.left
     
    # Perform rotation
    y.left = x
    x.right = T2
    
    update_sum(x)
    update_sum(y)
     
    # Return new root
    return y
 
def insert(root, key):
    # If root is None, create a new node and return it
    if not root:
        return TreapNode(key)
     
    # If key is smaller than root
    if key < root.key:
        # Insert in left subtree
        root.left = insert(root.left, key)
         
        # Fix Heap property if it is violated
        if root.left.priority > root.priority:
            root = rightRotate(root)
    else:
        # Insert in right subtree
        root.right = insert(root.right, key)
         
        # Fix Heap property if it is violated
        if root.right.priority > root.priority:
            root = leftRotate(root)
    update_sum(root)
    return root
 
def deleteNode(root, key):
    if not root:
        return root
     
    if key < root.key:
        root.left = deleteNode(root.left, key)
    elif key > root.key:
        root.right = deleteNode(root.right, key)
    else:
        # IF KEY IS AT ROOT
 
        # If left is None
        if not root.left:
            temp = root.right
            root = None
            return temp
 
        # If right is None
        elif not root.right:
            temp = root.left
            root = None
            return temp
         
        # If key is at root and both left and right are not None
        elif root.left.priority < root.right.priority:
            root = leftRotate(root)
            root.left = deleteNode(root.left, key)
        else:
            root = rightRotate(root)
            root.right = deleteNode(root.right, key)
    update_sum(root)
    return root

def print_treap(root):
    if root.left:
        print_treap(root.left)
    print('--', root.key, root.sum, root.size)
    if root.right:
        print_treap(root.right)

# A utility function to search a given key in a given BST
def search(root, key):
    # Base Cases: root is None or key is present at root
    if not root or root.key == key:
        return root
     
    # Key is greater than root's key
    if root.key < key:
        return search(root.right, key)
     
    # Key is smaller than root's key
    return search(root.left, key)

# 2 added functions for finding sum/cnt of elements >= target in the treap, both log(n):
def sum_bigger(root, key):
    if not root:
        return 0
    if root.key < key:
        return sum_bigger(root.right, key)
    else:
        l = sum_bigger(root.left, key)
        return root.sum - (0 if not root.left else root.left.sum) + l

def count_bigger(root, key):
    if not root:
        return 0
    if root.key < key:
        return count_bigger(root.right, key)
    else:
        l = count_bigger(root.left, key)
        return root.size - (0 if not root.left else root.left.size) + l

    
class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:
        n = len(colors)
        
        def seg_size(start, end):
            return (end - start + n) % n + 1
        
        def inc(p):
            return (p+1) % n
        
        def dec(p):
            return (p-1+n) % n
        
        is_loop = True
        segs = {} # seg[start] = end
        for i in range(n):
            if colors[inc(i)] == colors[i]:
                is_loop = False
                start = inc(i)
                break
                
        if is_loop:
            segs[0] = n - 1
        else:
            cur_start = start
            while True:
                cur = cur_start
                while colors[(cur+1)%n] != colors[cur]:
                    cur = inc(cur)
                segs[cur_start] = cur
                cur_start = inc(cur)
                # print(segs)
                if cur_start == start:
                    break
                    
        self.treap = None
        sl = SortedList()
        for start, end in segs.items():
            clen = seg_size(start, end)
            self.treap = insert(self.treap, clen)
            sl.add(start)
        
        # print('sl=', sl, 'segs=', segs)
        # print('treap:')
        # print_treap(self.treap)
        
        
        def add_seg(start, end):
            if start not in segs:
                segs[start] = end
                self.treap = insert(self.treap, seg_size(start, end))
                sl.add(start)
            
        def remove_seg(start, end):
            if start in segs:
                segs.pop(start)
                self.treap = deleteNode(self.treap, seg_size(start, end))
                sl.remove(start)
        
        res = []
        for q in queries:
            # print(segs, colors, sl)
            if q[0] == 1:
                ts = q[1]
                if len(segs) == 1:
                    start, end = list(segs.keys())[0], list(segs.values())[0]
                    if colors[end] != colors[start]: # loop
                        res.append(n)
                        continue
                # print('sum_bigger=', sum_bigger(self.treap, ts), 'count_bigger=', count_bigger(self.treap, ts))
                res.append(sum_bigger(self.treap, ts) - (ts-1) * count_bigger(self.treap, ts))
            else:
                p, c = q[1], q[2]
                if c != colors[p]:
                    
                    sl_p = sl.bisect_right(p) - 1
                    if sl_p < 0: # all starts are bigger than p
                        sl_p = len(sl)-1
                    # print(p, segs, sl)
                    start = sl[sl_p]
                    end = segs[start]
                    # handle single loop
                    if start == inc(end) and colors[start] != colors[end]:
                        remove_seg(start, end)
                        for s, e in [[p, p], [inc(p), dec(p)]]:
                            add_seg(s, e)
                        colors[p] = c
                        continue
                    
                    colors[p] = c
                    
                    s1 = [start, end]
                    startm1 = sl[sl_p-1]
                    endm1 = segs[startm1]
                    if startm1 == start:
                        s2 = s1
                    else:
                        s2 = [startm1, endm1]
                    startp1 = sl[(sl_p + 1) % len(sl)]
                    endp1 = segs[startp1]
                    if startp1 == start:
                        s3 = s1
                    elif startp1 == startm1:
                        s3 = s2
                    else:
                        s3 = [startp1, endp1]
                    
                    # print(segs, s2, s1, s3)
                    
                    for s, e in [s2, s1, s3]:
                        remove_seg(s, e)
                    if p == start and p == end:
                        s2[1] = p
                        s2[1] = s3[1]
                        add_seg(s2[0], s2[1])
                    elif p == start:
                        s2[1] = p
                        s1[0] = inc(p)
                        for s, e in [s2, s1, s3]:
                            add_seg(s, e)
                    elif p == end:
                        s1[1] = dec(p)
                        s3[0] = p
                        for s, e in [s2, s1, s3]:
                            add_seg(s, e)
                    else:
                        end = s1[1]
                        s1[1] = dec(p)
                        s5 = [inc(p), end]
                        for s, e in [s1, s5, [p, p], s2, s3]:
                            add_seg(s, e)
        return res
            
'''
[0,1,1,0,1]
[[2,1,0],[1,4]]
[0,0,1,0,1,1]
[[1,3],[2,3,0],[1,5]]
[0,0,0,1]
[[2,1,1],[1,3],[2,1,1],[2,0,1]]
[0,1,0,1]
[[1,3],[2,2,1],[1,3],[1,3]]
[1,0,1,0]
[[2,3,1],[1,3],[1,3],[1,3]]
'''      
40700