Binary Indexed Tree + Ordered Map
Intuition\n Describe your first thoughts on how to solve this problem. \nLet x represent the alternating groups with length = x, cnt[x] represent the number of 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet x represent the alternating groups with length = x, cnt[x] represent the number of groups with this length. Then to summarize the number of groups of length k, we have\n\n    sum(cnt[x] * (x - k + 1)) for x in [k, n]\n    => sum(cnt[x] * x) + sum(cnt[x] * (1-k))\n    => sum(cnt[x] * x) + (1 - k) * sum(cnt[x])\n\n    For example, k = 3 n = 6\n    length-3 alternating group count = cnt[3] * 1 + cnt[4] * 2 + cnt[5] * 3 + cnt[6] * 4\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse two binary indexed trees, one with value as `cnt[x] * x`, the other as `cnt[x]`. Apply the formula above to calculate total alternating groups of a specific length.\n\n# Complexity\n- Time complexity: O(qlogn) since each operation is logn\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```cpp []\nclass BIT {\n    vector<int> data;\n\n    int next(int i) {\n        return i + (i & -i);\n    }\n\n    int prev(int i) {\n        return i - (i & -i);\n    }\npublic:\n    BIT () {\n\n    }\n\n    BIT(int n) {\n        // offset = 1\n        data.resize(n + 1, 0);\n    }\n\n    void add(int i, int v) {\n        // i++;\n\n        while (i < data.size()) {\n            data[i] += v;\n            i = next(i);\n        }\n    }\n\n    int sum(int i) {\n        // i++;\n\n        int ans = 0;\n        while (i > 0) {\n            ans += data[i];\n            i = prev(i);\n        }\n\n        return ans;\n    }\n};\n\nclass Solution {\n    int n;\n    BIT bit1, bit0;\n\n    void update(int len, int cnt) {\n        bit0.add(len, cnt);\n        bit1.add(len, cnt * len);\n    }\n\n    int query(int len) {\n        int sum1 = bit1.sum(n);\n        int sum0 = bit0.sum(n);\n\n        if (len > 1) {\n            sum1 -= bit1.sum(len - 1);\n            sum0 -= bit0.sum(len - 1);\n        }\n\n        return sum1 + (1 - len) * sum0;\n    }\npublic:\n    /*\n    Let x represent the alternating groups with length = x,\n    cnt[x] represent the number of groups with this length.\n\n    Then to summarize the number of groups of length k, we have\n    sum(cnt[x] * (x - k + 1)) for x in [k, n-1]\n    => sum(cnt[x] * x) + sum(cnt[x] * (1-k))\n    => sum(cnt[x] * x) + (1 - k) * sum(cnt[x])\n\n    For example, k = 3 n = 7\n    length-3 alternating group count = cnt[3] * 2 + cnt[4] * 3 + cnt[5] * 4 + cnt[6] * 5\n\n    binary indexed tree; ordered map; binary search;\n    O(qlogn) time O(n) space;\n    */\n    vector<int> numberOfAlternatingGroups(vector<int>& colors, vector<vector<int>>& queries) {\n        n = colors.size();\n\n        // construct two Binary Index Trees\n        bit1 = BIT(n);\n        bit0 = BIT(n);\n\n        // continuous segments in colors[x...y]\n        map<int, int> group;\n        for (int i = 0, j = 0; j < n; j++) {\n            // end of alternating group\n            if (j + 1 == n || colors[j] == colors[j + 1]) {\n                group[i] = j;\n                update(j - i + 1, 1);\n                i = j + 1;\n            }\n        }\n\n\n        vector<int> ans;\n        for (auto &q : queries) {\n            if (q[0] == 1) {\n                // raw count, without considering wrap back\n                int val = query(q[1]);\n\n                // single big group ? \n                // [0,1,0,1,0] mp[0] = 4\n                if (group.size() == 1) {\n                    if (colors[0] != colors[n - 1]) {\n                        val = n;\n                    }\n\n                    // otherwise, remain raw query value\n                } else {\n                    if (colors[0] != colors[n - 1]) {\n                        auto first = group.begin();\n                        auto last = group.rbegin();\n                        int len1 = first->second - first->first + 1;\n                        int len2 = last->second - last->first + 1;\n                        // remove the contribution from len1 and len2 to q[1]\n                        val -= max(len1 - q[1] + 1, 0);\n                        val -= max(len2 - q[1] + 1, 0);\n                        val += max(len1 + len2 - q[1] + 1, 0);\n                    }\n                }\n                ans.push_back(val);\n            } else {\n                // type 2, modify colors array\n                int pos = q[1], val = q[2];\n                if (colors[pos] == val) {\n                    continue;\n                }\n\n                colors[pos] = val;\n                // [0,4] [5,5] [6,8] [9,10] pos=7 pos=6\n                auto it = group.upper_bound(pos);\n                it--;\n                // [l, r] of the modified group\n                int l = it->first, r = it->second;\n\n                // remove the old group\n                update(r - l + 1, -1);\n                group.erase(it);\n\n                // split into left and/or right groups\n                // consider cases\n                // pos = 3, [l, r]=[3,3]\n                //          [l, r]=[3,6]\n                //          [l, r]=[2,3]\n                //          [l, r]=[2,6]\n                // [start, end] range contains only pos, initially\n                int start = pos, end = pos;\n                if (l < pos) {\n                    group[l] = pos - 1;\n                    update(pos - 1 - l + 1, 1);\n                } else if (pos > 0) {\n                    // try connect left group with pos\n                    auto prev = group.upper_bound(pos);\n                    prev--;\n\n                    start = prev->first;\n                    update(prev->second - prev->first + 1, -1);\n                    group.erase(prev);\n\n                    // now [start, end=pos]\n                }\n\n                if (pos < r) {\n                    group[pos + 1] = r;\n                    update(r - (pos + 1) + 1, 1);\n                } else if (pos < n - 1) {\n                    auto next = group.upper_bound(pos);\n\n                    end = next->second;\n                    update(next->second - next->first + 1, -1);\n                    group.erase(next);\n\n                    // now [start, end]\n                }\n\n                // split in the middle [0,1,0,1,0] q=[2,2,1] start=2 end = 2\n                // connect one side    [0,1,0,0,1,1,0,1] q=[2,3,1] start=0 end=3\n                // connect both sides  [0,1,0,0,0,1,0] q=[2,3,1] start=0 end=6\n                // std::cout << start << " " << end << std::endl;\n                group[start] = end;\n                update(end - start + 1, 1);\n            }\n        }\n\n        return ans;\n    }\n};\n```
['C++']