[Javascript] AVL tree + Fenwick tree
\n\n/**\n * @param {number[]} colors\n * @param {number[][]} queries\n * @return {number[]}\n */\n\nclass TreeNode {\n    constructor(key, value, left=null, rig
\n```\n/**\n * @param {number[]} colors\n * @param {number[][]} queries\n * @return {number[]}\n */\n\nclass TreeNode {\n    constructor(key, value, left=null, right=null, height=1) {\n        this.key = key;\n        this.value = value;\n        this.left = left;\n        this.right = right;\n        this.height = height;\n    }\n}\n\n\nclass AVLTree {\n    /*The AVL tree, named after its inventors Georgy Adelson-Velsky and\n    Evgenii Landis, in their 1962 paper \u201CAn algorithm for the organization of\n    information\u201D, is a self-balancing Binary Search Tree (BST) where the\n    difference between heights of left and right subtrees for any node cannot be\n    more than one.*/\n    constructor() {\n        this.root = null;\n        this.size = 0;\n    }\n\n    balance(node) {\n        if (!node) return 0;\n        return this.height(node.left) - this.height(node.right);\n    }\n\n    /*Returns a key-value mapping associated with the least key greater than or\n    equal to the given key, or null if there is no such key.*/\n    ceilingEntry(key) {\n        let ans = null;\n        let node = this.root;\n        while (node)\n            if (node.key < key) node = node.right;\n            else {\n                ans = node;\n                node = node.left;\n            }\n        return ans;\n    }\n\n    firstEntry() {\n        return this.#firstEntry(this.root);\n    }\n\n    /*Returns a key-value mapping associated with the greatest key less than or\n    equal to the given key, or null if there is no such key.*/\n    floorEntry(key) {\n        let ans = null;\n        let node = this.root;\n        while (node)\n            if (key < node.key) node = node.left;\n            else {\n                ans = node;\n                node = node.right;\n            }\n        return ans;\n    }\n\n    get(key) {\n        return this.#get(this.root, key);\n    }\n\n    height(node) {\n        if (!node) return 0;\n        return node.height;\n    }\n\n    put(key, value=0) {\n        this.root = this.#put(this.root, key, value);\n    }\n\n    remove(key) {\n        this.root = this.#remove(this.root, key);\n    }\n\n    #firstEntry(node) {\n        while (node && node.left) node = node.left;\n        return node;\n    }\n\n    #get(node, key) {\n        if (!node) return null;\n        if (node.key === key) return node.value;\n        if (node.key < key) return this.#get(node.right, key);\n        return this.#get(node.left, key);\n    }\n\n    #put(node, key, value) {\n        if (!node) {\n            ++this.size;\n            return new TreeNode(key, value);\n        } else if (key < node.key) node.left = this.#put(node.left, key, value);\n        else if (key > node.key) node.right = this.#put(node.right, key, value);\n        else {\n            node.value = value;\n            return node;\n        }\n        node.height = 1 + Math.max(this.height(node.left), this.height(node.right));\n        let bal = this.balance(node);\n        if (bal > 1 && key < node.left.key)\n            return this.right_rotate(node);\n        if (bal < -1 && key > node.right.key)\n            return this.left_rotate(node);\n        if (bal > 1 && key > node.left.key) {\n            node.left = this.left_rotate(node.left);\n            return this.right_rotate(node);\n        }\n        if (bal < -1 && key < node.right.key) {\n            node.right = this.right_rotate(node.right);\n            return this.left_rotate(node);\n        }\n        return node;\n    }\n\n    #remove(node, key) {\n        if (!node) return node;\n        if (key < node.key) node.left = this.#remove(node.left, key);\n        else if (key > node.key) node.right = this.#remove(node.right, key);\n        else {\n            if (!node.left) {\n                let temp = node.right;\n                node = null;\n                --this.size;\n                return temp;\n            }\n            if (!node.right) {\n                let temp = node.left;\n                node = null;\n                --this.size;\n                return temp;\n            }\n            let temp = this.#firstEntry(node.right);\n            node.key = temp.key;\n            node.value = temp.value; \n            node.right = this.#remove(node.right, temp.key);\n        }\n        if (!node) return node;\n        node.height = 1 + Math.max(this.height(node.left), this.height(node.right));\n        let bal = this.balance(node);\n        if (bal > 1 && this.balance(node.left) > 0)\n            return this.right_rotate(node);\n        if (bal < -1 && this.balance(node.right) < 0)\n            return this.left_rotate(node);\n        if (bal > 1 && this.balance(node.left) < 0) {\n            node.left = this.left_rotate(node.left);\n            return this.right_rotate(node);\n        }\n        if (bal < -1 && this.balance(node.right) > 0) {\n            node.right = this.right_rotate(node.right);\n            return this.left_rotate(node);\n        }\n        return node;\n    }\n\n    left_rotate(node) {\n        let y = node.right, T2 = y.left;\n        y.left = node;\n        node.right = T2;\n        node.height = 1 + Math.max(this.height(node.left), this.height(node.right));\n        y.height = 1 + Math.max(this.height(y.left), this.height(y.right));\n        return y;\n    }\n\n    right_rotate(node) {\n        let y = node.left, T3 = y.right;\n        y.right = node;\n        node.left = T3;\n        node.height = 1 + Math.max(this.height(node.left), this.height(node.right));\n        y.height = 1 + Math.max(this.height(y.left), this.height(y.right));\n        return y;\n    }\n\n    entrySet() {\n        return this.traverse().map(x => [x.key, x.value]);\n    }\n\n    toString() {\n        return "{" + this.traverse().map(x => x.key + " : " + x.value).join(", ") + "}";\n    }\n\n    traverse() {\n        const ans = [], stack = [];\n        let node = this.root;\n        while (stack.length || node)\n            if (node) {\n                stack.push(node);\n                node = node.left;\n            } else {\n                node = stack.pop();\n                ans.push(node);\n                node = node.right;\n            }\n        return ans;\n    }\n}\n\nclass Fenwick {\n    constructor(n) {\n        this.cnts = Array(n+1).fill(0); \n        this.vals = Array(n+1).fill(0); \n    }\n    \n    add(k, v) {\n        for (let i = k+1; i < this.cnts.length; i += i & -i) {\n            this.cnts[i] += v; \n            this.vals[i] += v*k; \n        }\n    }\n    \n    query(k, v) {\n        let ans = 0; \n        for (let i = k+1; i; i -= i & -i) \n            ans += this.vals[i] - v*this.cnts[i]; \n        return ans; \n    }\n}\n\n\nvar numberOfAlternatingGroups = function(colors, queries) {\n    const n = colors.length; \n    const groups = new AVLTree(); \n    for (let i = 0, j = 0; i < n; i = j+1) {\n        for (j = i; j < i+n-1 && colors[j%n] != colors[(j+1)%n]; ++j); \n        groups.put(j%n, i); \n    }\n    const fen = new Fenwick(n+1); \n    \n    var dist = (lo, hi) => lo <= hi ? hi-lo+1 : n+hi-lo+1; \n    \n    var add = function(lo, hi) {\n        groups.put(hi, lo); \n        fen.add(dist(lo, hi), 1); \n    }; \n    \n    var remove = function(i) {\n        let hi = groups.ceilingEntry(i); \n        if (hi == null) hi = groups.firstEntry().key; \n        else hi = hi.key; \n        const lo = groups.get(hi); \n        groups.remove(hi); \n        fen.add(dist(lo, hi), -1); \n        return [lo, hi]; \n    }; \n    \n    for (const [j, i] of groups.entrySet()) {\n        add(i, j); \n    }\n    const ans = []; \n    for (const q of queries) {\n        if (q[0] === 1) {\n            if (groups.size == 1 && colors[groups.firstEntry().key] != colors[groups.firstEntry().value]) ans.push(n); \n            else {\n                const sz = q[1]; \n                ans.push(fen.query(n, sz-1) - fen.query(sz-1, sz-1)); \n            }\n        } else {\n            const i = q[1], c = q[2]; \n            if (colors[i] != c) {\n                colors[i] = c; \n                let [lo, hi] = remove(i); \n                if (lo == hi) {\n                    if (colors[(i-1+n)%n] != colors[i]) lo = remove((i-1+n)%n)[0]; \n                    if (colors[i] != colors[(i+1)%n] && groups.size) hi = remove((i+1)%n)[1]; \n                    add(lo, hi); \n                } else if (lo == i) {\n                    add((i+1)%n, hi); \n                    if (colors[(i-1+n)%n] != colors[i]) lo = remove((i-1+n)%n)[0]; \n                    add(lo, i); \n                } else if (i == hi) {\n                    add(lo, (i-1+n)%n); \n                    if (colors[i] != colors[(i+1)%n]) hi = remove((i+1)%n)[1]; \n                    add(i, hi); \n                } else {\n                    const i0 = (i-1+n)%n, i1 = (i+1)%n; \n                    if (dist(lo, hi) == n && colors[lo] != colors[hi]) add(i1, i0); \n                    else {\n                        add(lo, i0); \n                        add(i1, hi); \n                    }\n                    add(i, i); \n                }\n            }\n        }\n    }\n    return ans; \n};\n```
['JavaScript']