O(N^1.5) in Python3 with Explanation, Faster than 100%
Approach\nFirstly I solve the simpler, non-circular version of this problem. I maintain all the valid segments and the counts of their lengths, and the answer c
# Approach\nFirstly I solve the simpler, non-circular version of this problem. I maintain all the valid segments and the counts of their lengths, and the answer can be easily computed in $O(\\sqrt{N})$ since there are at most $O(\\sqrt{N})$ kinds of lengths. \n\nFor update, an update on a position $i$ will break a valid segment $(l, r)$ where $l \\le i \\le r$ into three segments $(l, i-1)$, $(i, i)$, and $(i+1, r)$, or merge three valid segments $(l, i-1)$, $(i, i)$, and $(i+1, r)$ into one $(l, r)$. So, use an efficient data structure like binary searc tree or `sortedcontainers` to maintain those segments and their lengths. As a result, each udpate can be accomplished in $O(\\log N)$ (with BST) or $O(\\sqrt{N})$ (with `SortedList` in Python3). \n\nThe idea is simple, but the implementation is lengthy because of the edge cases such as $i = 0$ or $i = N-1$. This is perhaps the problem I solved using the longest code.    \n\nFinally, the solution of the non-circular simplied problem can be extended to the circular version by a simple check of the first segment and the last segment if they can be merged into a valid segment during each query.  \n\n# Complexity\n- Time complexity: $O(N \\sqrt{N})$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n                \n        n = len(colors)\n        cnt = defaultdict(int)\n        groups = SortedList()\n        \n        def count(target_len):\n            return sum((l - target_len + 1) * c for l, c in cnt.items()\n if l >= target_len)\n\n        def query(target_len):\n            if colors[n-1] == colors[0]:\n                return count(target_len)\n            if len(groups) == 1:\n                return n\n            first, last = groups[0], groups[-1]\n            l1, l2 = first[1] - first[0] + 1, last[1] - last[0] + 1\n            cnt[l1] -= 1\n            cnt[l2] -= 1\n            cnt[l1+l2] += 1\n            r = count(target_len)\n            cnt[l1] += 1\n            cnt[l2] += 1\n            if cnt[l1+l2] == 1:\n                del cnt[l1+l2]\n            else:   \n                cnt[l1+l2] -= 1\n            return r\n            \n        def add_group(l, r):\n            groups.add((l, r))\n            cnt[r - l + 1] += 1\n\n        def remove_group(l, r):\n            groups.remove((l, r))\n            if cnt[r-l+1] == 1:\n                del cnt[r-l+1]\n            else:\n                cnt[r - l + 1] -= 1\n            \n        l = 0\n        for r in range(1, len(colors)):\n            if colors[r] == colors[r-1]:\n                add_group(l, r-1)\n                l = r\n        add_group(l, n - 1)\n        ans = []\n        for q in queries:\n            if len(q) == 2:\n                ans.append(query(q[1])) \n            else:\n                (idx, color) = q[1:]\n                if colors[idx] == color:\n                    continue    # Nothing change\n                colors[idx] = color\n                p = groups.bisect_left((idx, -inf))\n                if p < len(groups) and groups[p][0] == idx:\n                    if groups[p][1] == idx:\n                        l, r = idx, idx\n                        if p + 1 < len(groups):\n                            l2, r = groups[p+1]\n                            remove_group(l2, r)\n                        remove_group(*groups[p])\n                        if p > 0:\n                            l, r2 = groups[p-1]\n                            remove_group(l, r2)\n                        add_group(l, r)\n                    else:\n                        l, r = groups[p]\n                        remove_group(l, r)\n                        add_group(l + 1, r)\n                        if p > 0:\n                            l2, r2 = groups[p-1]\n                            remove_group(l2, r2)\n                            add_group(l2, idx)\n                        else:\n                            add_group(idx, idx)\n                else:\n                    p -= 1\n                    if groups[p][1] == idx:\n                        if p + 1 < len(groups):\n                            l, r = groups[p+1]\n                            remove_group(l, r)\n                            add_group(idx, r)\n                        else:\n                            add_group(idx, idx)\n                        l, r = groups[p]\n                        remove_group(l, r)\n                        add_group(l, idx-1)\n                    else:\n                        l, r = groups[p]\n                        remove_group(l, r)\n                        add_group(l, idx-1)\n                        add_group(idx, idx)\n                        add_group(idx+1, r)\n        return ans\n```
['Binary Search Tree', 'Python3']