Two Fenwick trees and a balanced search tree, running in O(n log n)
Intuition\nGive a maximal alternating interval of size $m$, it contains $m-k+1$ intervalls of size $k \le m$. Hence, if we know the number $A_m$ of all maximal 
# Intuition\nGive a maximal alternating interval of size $m$, it contains $m-k+1$ intervalls of size $k \\le m$. Hence, if we know the number $A_m$ of all maximal intervalls of size $m$ for each length $m$, we can compute the total number $n_k$ of intervalls of size $k$ by $$n_k = \\sum_{i=k}^n (i - k + 1) A_i.$$ Since updating the $A_i$ for each update query is possible in $O(1)$, we need a fast way to compute the above sums (which would otherwise be $O(n)$). Following the hint, we use Fenwick trees.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe basic idea is to use *two* Fenwick trees/BIT, one for computing the usual sums $$A(i,j] := \\sum_{k=i+1}^j A_k$$ and a second one to compute the sums $$B(i,j] := \\sum_{k=i+1}^j kA_k$$. Note that $B(i,j]$ also satisfies the important property $$B(i,j] + B(j, k] = B(i, k]$$, which is the reason why BIT work.\n\nThe final observation is that we can compute $n_k$ with the help of $A(i,j]$ and $B(i,j]$:\n\n$$n_k = \\sum_{i=k}^n (i - k + 1) A_i = \\sum_{i=k}^n i A_i - (k-1)\\sum_{i=k}^n A_i = B(k-1,n] - (k-1) A(k-1,n]$$\n\nBecause the computation of $B(i,j]$ and $A(i,j]$ is possible in $O(\\log n)$ in BIT, we can compute $n_k$ in $O(\\log n)$ as well.\n\nHandling the maximal intervalls is done using a balanced search-tree with a constant number of accesses for each query, hence runs in $O(\\log n)$ as well.\n\n# Complexity\n- Time complexity: $O(n \\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```\nuse std::collections::BTreeSet;\n\nimpl Solution {\n    pub fn number_of_alternating_groups(mut colors: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {\n        let n = colors.len();\n        let mut ft = FTree::new(n);\n        let mut invs= BTreeSet::new();\n\n        if let Some(s) = (0..n).position(|i| colors[(i + n - 1) % n] == colors[i]) {\n            // found split position s, the first interval is [s,...)\n            let mut i = s;\n            loop {\n                invs.insert(i); // add the start of the interval\n                // find end of interval\n                let mut j = (i + 1) % n;\n                while colors[j] != colors[(j + n - 1) % n] {\n                    j = (j + 1) % n;\n                }\n                let l = (j + n - i) % n;\n                ft.add(if l == 0 { n } else { l }, 1);\n                i = j;\n                if i == s {\n                    break;\n                }\n            }\n        } else {\n            // a single consecutive interval, this is a special case\n            invs.insert(0);\n            ft.add(n, 1);\n        }\n\n        let mut results = vec![];\n        for q in queries {\n            if q[0] == 1 {\n                results.push(query(q[1] as usize, &ft, &invs));\n            } else {\n                toggle(q[1] as usize, q[2], &mut ft, &mut invs, &mut colors);\n            }\n        }\n\n        results\n    }\n}\n\nfn toggle(i: usize, c: i32, ft: &mut FTree, invs: &mut BTreeSet<usize>, colors: &mut Vec<i32>) {\n    if colors[i] == c {\n        return;\n    }\n\n    // switch color\n    colors[i] = c;\n\n    // find the interval [a,b) containing i\n    let n = colors.len();\n    let (a, b) = find_containing_interval(invs, i);\n    let s = (b + n - a) % n;\n\n    if a == b {\n        // there is only one interval (of size n) -> special case\n        if n % 2 == 1 {\n            // odd cycle\n            if (i + 1) % n == a {\n                // odd cycle, the non-matching end is shifted by -1, the number of intervals does not change\n                invs.clear();\n                invs.insert(i);\n            } else if i == a {\n                // odd cycle, the non-matching end is shifted by +1, the number of intervals does not change\n                invs.clear();\n                invs.insert((i + 1) % n);\n            } else {\n                // insert a singleton, splitting the rest\n                invs.insert(i);\n                invs.insert((i + 1) % n);\n                let left_s = (i + n - a) % n;\n                let right_s = (b + n - (i + 1)) % n;\n                ft.add(n, -1);\n                ft.add(left_s, 1);\n                ft.add(right_s, 1);\n            }\n        } else {\n            // even cycle\n            ft.add(n, -1);\n            ft.add(n - 1, 1);\n            ft.add(1, 1);\n            invs.clear();\n            invs.insert(i);\n            invs.insert((i + 1) % n);\n        }\n    } else if s == 1 {\n        // i is currently a singleton, switching its color connects *both* adjacent intervals\n        // we simply remove both boundaries\n        invs.remove(&a);\n        invs.remove(&b);\n        if invs.is_empty() {\n            // special case, this was the last singleton!!\n            invs.insert(0);\n            ft.add(1, -1);\n            ft.add(n - 1, -1);\n            ft.add(n, 1);\n            return;\n        }\n        let (new_a, new_b) = find_containing_interval(invs, i);\n        let left_s = (i + n - new_a) % n;\n        let right_s = (new_b + n - (i + 1)) % n;\n        let mut new_s = (new_b + n - new_a) % n;\n        if new_s == 0 {\n            // special case: only one interval remaining\n            new_s = n\n        };\n        ft.add(1, -1);\n        ft.add(left_s, -1);\n        ft.add(right_s, -1);\n        ft.add(new_s, 1);\n    } else if i == a {\n        // i is at the left boundary\n        // i switches to the interval to the left\n        let (left_a, left_b) = find_containing_interval(invs, (i + n - 1) % n);\n        let left_s = (left_b + n - left_a) % n;\n        debug_assert_eq!(left_b, a);\n        ft.add(s, -1);\n        ft.add(left_s, -1);\n        ft.add(s - 1, 1);\n        ft.add(left_s + 1, 1);\n        invs.remove(&i);\n        invs.insert((i + 1) % n);\n    } else if (i + 1) % n == b {\n        // i is at the right boundary\n        // i switches to the interval to the right\n        let (right_a, right_b) = find_containing_interval(invs, (i + 1) % n);\n        let right_s = (right_b + n - right_a) % n;\n        debug_assert_eq!(right_a, b);\n        ft.add(s, -1);\n        ft.add(right_s, -1);\n        ft.add(s - 1, 1);\n        ft.add(right_s + 1, 1);\n        invs.remove(&((i + 1) % n));\n        invs.insert(i);\n    } else {\n        // is in the middle of [a,b)\n        // this will split the interval in two halfs [a,i), [i+1, b) and one singleton [i,i+1)\n        let left_s = (i + n - a) % n;\n        let right_s = (b + n - (i + 1)) % n;\n        ft.add(s, -1);\n        ft.add(1, 1);\n        ft.add(left_s, 1);\n        ft.add(right_s, 1);\n        invs.insert(i);\n        invs.insert((i + 1) % n);\n    }\n}\n\nfn find_containing_interval(invs: &BTreeSet<usize>, i: usize) -> (usize, usize) {\n    let a = invs.range(..=i).next_back().or_else(|| invs.last()).unwrap().clone();\n    let b = invs.range(i + 1..).next().or_else(|| invs.first()).unwrap().clone();\n    (a, b)\n}\n\nfn query(i: usize, a: &FTree, invs: &BTreeSet<usize>) -> i32 {\n    let n = a.size();\n    if n % 2 == 0 && invs.len() <= 1 {\n        return n as i32;\n    }\n    let p1 = a.prefix(n);\n    let p2 = a.prefix(i - 1);\n    let y = p1.1 - p2.1;\n    let x = p1.0 - p2.0;\n    y - (i - 1) as i32 * x\n}\n\nstruct FTree {\n    tree: Vec<(i32, i32)>,\n}\n\nimpl FTree {\n    fn new(n: usize) -> FTree {\n        FTree {\n            tree: vec![(0, 0); n + 1],\n        }\n    }\n\n    fn size(&self) -> usize {\n        self.tree.len() - 1\n    }\n\n    /// Add `value` to `A[i]`\n    fn add(&mut self, i: usize, value: i32) {\n        let mut j = i;\n        while j < self.tree.len() {\n            self.tree[j].0 += value;\n            self.tree[j].1 += value * i as i32;\n            j += lsb(j);\n        }\n    }\n\n    /// Return A(0,i]\n    fn prefix(&self, i: usize) -> (i32, i32) {\n        let mut sum0 = 0;\n        let mut sum1 = 0;\n        let mut i = i;\n        while i > 0 {\n            sum0 += self.tree[i].0;\n            sum1 += self.tree[i].1;\n            i -= lsb(i);\n        }\n        (sum0, sum1)\n    }\n}\n\nfn lsb(i: usize) -> usize {\n    i & (-(i as i64) as usize)\n}\n\n```
['Rust']