O(nlogn)-time; Binary indexed tree and SortedList
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to do the following jobs on-line:\n1. maintain the alternative intervals; and \
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to do the following jobs on-line:\n1. maintain the alternative intervals; and \n2. count the number of alternative intervals of given size.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe intervals are maintained by storing their ends in a SortedList, and the counting job is done by employing two binary indexed trees.\nIf $a[i]$ is the number of intervals of length $i$. One BIT stores $a[i]$, the amount of every length, and the other stores $i\\times a[i]$. For query of length $j$, we need to compute $\\sum_{i\\geq j}a[i]\\times (i-j+1)$, which can be done by performing prefix sums on the two BITs.\n\nThere are some special edge cases to be considered, especially when the entire array is alternative, for both odd and even $n$.\n\n\n# Complexity\n- Time complexity:$O(q\\log n)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfrom sortedcontainers import SortedList\nclass Bit:\n    def __init__(self,n):\n        self.bit = [0]*(n+1)\n        self.wbit = [0]*(n+1)\n        self.n = n\n        self.total = 0\n        self.wtotal = 0\n        \n    def modi(self,i,x):\n        if i<2: return\n        w = i*x\n        self.total += x\n        self.wtotal += w\n        while i<=self.n:\n            self.bit[i] += x\n            self.wbit[i] += w\n            i += i&(-i)\n            \n    def query(self,i): # sum((j-i+1)*a[j] for j >=i)\n        w = v = 0\n        i -= 1\n        s = i\n        while i>0:\n            w += self.wbit[i]\n            v += self.bit[i]\n            i -= i&(-i)\n        return self.wtotal-w - (self.total-v)*s \n        \nclass Solution:\n    def numberOfAlternatingGroups(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n        n = len(colors)\n        cnt = Bit(n)\n        #print(\'bit init\')\n        t = [i for i in range(n-1) if colors[i] == colors[i+1]]\n        if colors[n-1]==colors[0]: t.append(n-1)\n        end = SortedList(t)\n        if end:\n            c = Counter(v-u for u,v in zip(t,t[1:]))\n            c[t[0]+n-t[-1]] += 1\n            for v,k in c.items(): cnt.modi(v,k)\n        else: cnt.modi(n,1)\n        \n        ans = []\n        for q in queries:\n            if q[0]==1:\n                if end: ans.append(cnt.query(q[1]))\n                else: # entire cycle\n                    ans.append(n)\n                continue\n            # q[0]==2\n            idx,col = q[1],q[2]\n            if colors[idx]==col: continue\n            colors[idx]=col\n            sameprev = bool(colors[idx]==colors[idx-1])\n            samenext = bool(colors[idx]==colors[(idx+1)%n])\n            if sameprev and samenext: # split\n                if not end: # no end, leng=n\n                    end.add((idx-1)%n)\n                    end.add(idx)\n                    cnt.modi(n,-1)\n                    cnt.modi(n-1,1)\n                    continue\n                # otherwise\n                i = end.bisect_left(idx)\n                leng = (end[i%len(end)]-end[i-1])%n # maybe first\n                if leng==0: leng=n\n                cnt.modi(leng,-1)\n                l1 = (idx-1-end[i-1])%n\n                cnt.modi(l1,1)\n                cnt.modi(leng-l1-1,1)\n                end.add((idx-1)%n)\n                end.add(idx)\n            elif (not sameprev) and (not samenext):\n                #merge, [,idx-1][idx,idx][idx+1,]\n                if len(end)==2:\n                    end.clear()\n                    cnt.modi(n-1,-1)\n                    cnt.modi(n,1)\n                    continue\n                i = end.bisect_left(idx) # must exist\n                l1 = (end[i-1]-end[i-2])%n\n                l2 = (end[(i+1)%len(end)]-end[i])%n\n                end.remove(idx)\n                end.remove((idx-1)%n)\n                cnt.modi(l1,-1)\n                cnt.modi(l2,-1)\n                cnt.modi(l1+l2+1,1)\n                # impossible empty end\n            elif sameprev and (not samenext): # move idx to head of next\n                # [,idx][idx+1,]\n                i = end.bisect_left(idx) # must exist\n                l1 = (end[i]-end[i-1])%n\n                l2 = (end[(i+1)%len(end)]-end[i])%n\n                end.remove(idx)\n                end.add((idx-1)%n)\n                cnt.modi(l1,-1)\n                cnt.modi(l1-1,1)\n                cnt.modi(l2,-1)\n                cnt.modi(l2+1,1)\n            elif (not sameprev) and samenext: # move idx to tail of prev\n                # [,idx-1][idx,]\n                i = end.bisect_left((idx-1)%n) # must exist\n                l1 = (end[i]-end[i-1])%n\n                l2 = (end[(i+1)%len(end)]-end[i])%n\n                end.remove((idx-1)%n)\n                end.add(idx)\n                cnt.modi(l1,-1)\n                cnt.modi(l1+1,1)\n                cnt.modi(l2,-1)\n                cnt.modi(l2-1,1)\n        # end for query\n        return ans\n```
['Binary Indexed Tree', 'Python3']