qsqrt(n) + qlogn python solution with comments and explanation
Intuition\nFirst, let\'s make the idea of a circular array more intuitive. If we have the array A: [0, 1, 0, 1, 1], we can add it to itself denote as A\': [0, 1
# Intuition\nFirst, let\'s make the idea of a circular array more intuitive. If we have the array ``A``: ``[0, 1, 0, 1, 1]``, we can add it to itself denote as ``A\'``: ``[0, 1, 0, 1, 1, 0, 1, 0, 1, 1]``. You can see that ``A\'`` contains all shifts of ``A``.\n\nNext, if we have a segment of length x, it contains: \n```\n2 segments of length x-1\n3 segments of length x-2\n4 segments of length x-3 \n...and so on.\n```\nTherefore, we can sweep across the array and find all the alternating segments. The answer to a ``[1, x]`` query is ``sum((length-x+1)*amt for length, amt in count)``, where ``count[l]`` denotes how many segments have length ``l``. ``count`` cannot have more than $$sqrt(n)$$ entries, because $$1+2+3+4+5+6... N = (N+1)*N/2$$. We must also consider a segment that goes over ``n``, as we may overcount(details in code). Queries of type 1 can be answered in $$sqrt(n)$$ using this method. \n\nFor queries of type two, we must consider the following cases(place them on paper for better understanding):\n1. Query index is **inside** a segment.\n    - This splits the segment into 3 pieces\n2. Query index is **on the edge** of a segment.\n    - The left segment is expanded by one, the right segment is shrunk by one.\n3. Query index is **inside a segment of length one**.\n    - The segment to the left is merged with the segment to the right.\n\nTo find the segment where the query index lies, we can use binary search.\n``count`` and ``segments`` are now easy to update in $$logn$$ time.\n\nImplementation details are in the code.\n# Code\n```\nfrom sortedcontainers import SortedList\nclass Solution:\n    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n\n        n = len(colors)\n        colors+=colors\n        prev = -1\n        left = 0\n        segments = SortedList()\n        for i, x in enumerate(colors):\n            if prev == -1:\n                prev = x\n                continue\n\n            if x == prev:\n                segments.add((left, i))\n                left = i\n            prev = x\n\n        segments.add((left, len(colors)))\n\n        cnt = Counter()\n        for x, y in segments:\n            if y <= n:\n                cnt[y-x] += 1\n\n        def bsearch(idx):\n            l = 0\n            r = len(segments)-1\n            while l <= r:\n                mid = (l+r)//2\n                x, y = segments[mid]\n                if x <= idx < y:\n                    return mid\n                if idx < x:\n                    r = mid-1\n                else:\n                    l = mid+1\n\n            return 0\n\n        def update(idx):\n            i = bsearch(idx)\n            x, y = segments[i]\n            \n            newsegs = []\n            remove = []\n            # in middle\n            if x < idx < y-1:\n                newsegs.append((x, idx))\n                newsegs.append((idx, idx+1))\n                newsegs.append((idx+1, y))\n                remove.append((x, y))\n            # on an edge\n            else:\n                remove.append((x, y))\n                # inside a segment of length one\n                if idx == x and idx == y-1:\n                    left = x\n                    right = y\n                    if i-1 >= 0:\n                        prevx, prevy = segments[i-1]\n                        left = prevx\n                        remove.append((prevx, prevy))\n                    if i+1 < len(segments):\n                        nxtx, nxty = segments[i+1]\n                        right = nxty\n                        remove.append((nxtx, nxty))\n                    newsegs.append((left, right))\n                # on left edge\n                elif idx == x:\n                    if i-1 >= 0:\n                        prevx, prevy = segments[i-1]\n                        remove.append((prevx, prevy))\n                        newsegs.append((prevx, prevy+1))\n                    else:\n                        newsegs.append((0, 1))\n                    newsegs.append((x+1, y))\n                # on right edge\n                else:\n                    if i+1 < len(segments):\n                        nxtx, nxty = segments[i+1]\n                        remove.append((nxtx, nxty))\n                        newsegs.append((nxtx-1, nxty))\n                    else:\n                        newsegs.append((len(colors)-1, len(colors)))\n                    newsegs.append((x, y-1))\n            # update count and segments\n            for seg in remove:\n                segments.remove(seg)\n                if seg[1] <= n:\n                    cnt[seg[1]-seg[0]] -= 1\n\n            for seg in newsegs:\n                if seg[0] == seg[1]:\n                    continue\n                segments.add(seg)\n                if seg[1] <= n:\n                    cnt[seg[1]-seg[0]] += 1\n\n        res = []\n        for q in queries:\n            if q[0] == 1:\n                x = q[1]\n                ans = 0\n                todel = []\n                for length, amt in cnt.items():\n                    # no more, delete from dict\n                    if amt == 0:\n                        todel.append(length)\n                    if length >= x:\n                        ans += (length-x+1)*amt\n                for length in todel:\n                    del cnt[length]\n                # find segment that goes over n\n                edgeidx = bsearch(n)\n                left, right = segments[edgeidx]\n                length = right-left\n\n                ans += max(0, min(length-x+1, n-left))\n                res.append(ans)\n            else:\n                # didn\'t change\n                if q[2] == colors[q[1]]:\n                    continue\n                colors[q[1]] = q[2]\n                idx1 = q[1]\n                idx2 = n+idx1\n                # update index and rotated index\n                update(idx1)\n                update(idx2)\n                \n        return res\n```
['Python3']