python solution store all end indexes, Counter segment size
Intuition\n Describe your first thoughts on how to solve this problem. \nWe store all indexes i that colors[i]==colors[i+1] (colors[n] is colors[0]) in a Sorted
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe store all indexes i that colors[i]==colors[i+1] (colors[n] is colors[0]) in a SortedList sl. From that we can calculate the size of each segments with alternating color, and store the size in a counter. counter will have maximum size sqrt(n) (containing 1,2,3,4,...) \nHandle special case when len(sl)==0, len(sl)<5 \nFor each query 2, if colors[i]!=new color, we toggle prev and i in sl. If len(sl) is small we can directly recompute count. Else we check each case and update count.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(sqrt(n) * q)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\nfrom sortedcontainers import SortedList\nclass Solution:\n    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n        n, sl = len(colors), SortedList()\n        for i in range(1, n):\n            if colors[i-1]==colors[i]: sl.add(i)\n        if colors[0]==colors[n-1]: sl.add(n)\n        def buildc():\n            count=Counter()\n            if len(sl)==0: return count\n            prev = sl[-1]-n\n            for i in sl:\n                count[i-prev]+=1\n                prev=i\n            return count\n        count = buildc()\n        def getsl(ind):\n            if ind<0: return sl[ind + len(sl)] - n\n            if ind>=len(sl): return sl[ind - len(sl)] + n\n            return sl[ind]\n        def inc(v):\n            count[v]+=1\n        def dec(v):\n            count[v]-=1\n            if count[v]==0: count.pop(v)\n        def toggle(i):\n            ind = sl.bisect_left(i)\n            if getsl(ind)==i:\n                lo,hi = getsl(ind-1), getsl(ind+1)\n                dec(i-lo)\n                dec(hi-i)\n                inc(hi-lo)\n                sl.remove(i)\n            else:\n                lo,hi = getsl(ind-1), getsl(ind)\n                inc(i-lo)\n                inc(hi-i)\n                dec(hi-lo)\n                sl.add(i)\n        def qr1(size):\n            if len(sl)==0: return n\n            return sum(max(0, a-size+1)*b for a,b in count.items())\n        answer = []\n        for q in queries:\n            if q[0]==1: \n                answer.append(qr1(q[1]))\n                continue\n            index, color = q[1], q[2]\n            if colors[index]==color: continue\n            colors[index]=color\n            z = [(n if index==0 else index), index+1]\n            if len(sl)<=5:\n                for i in z:\n                    if i in sl: sl.remove(i)\n                    else: sl.add(i)\n                count = buildc()\n            else:\n                for i in z: toggle(i)\n        return answer\n```
['Python3']