[c++] Using Map instead of Segment Tree
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nSimilar as the Meeting 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSimilar as the Meeting Room problem, use (ordered) map instead of segment tree.\n\nmap key -> range start  \nmap value-> range end\nEach position will always belong to one range\nThe position with next neigbour that has the same value, is with range of length of 1.\nLog(n) to find the which position belong to which range.\nWe apply similar logic of split and merge segment as the Meeting Room problem.\n\nHow to caculate Total number of alternating groups with size i\nKeep track number of all length of segment in another map.\n\n\nHow do we deal with circularly array:\nThe trick is We dont care about circular array when we update the array or update the range map.\nWe only check circularly array when counting the alternating groups with size i, just check if start of array is different fromend of array, if so, we recaculate the 1st segment connect with last segment and minus 1st segment and last segment\'s contribution.\n\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nLog(n) for each update.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> dp;\n    int n;\n    map<int, int> mp;\n    map<int, int> cnt;\n\n    int count(int x)\n    {\n        auto iter = cnt.rbegin();\n        int ans = 0;\n        if (iter->first == n && (dp[0] != dp[n- 1]))\n        {\n            ans += n;\n            return ans;\n        }\n        while (iter != cnt.rend())\n        {\n            if (iter->first < x) break;\n            ans += (iter->first + 1 - x) * iter->second;\n            iter++;\n        }\n        \n        if (mp.size() >= 2 + 2)\n        {\n            if (dp[0] != dp[n - 1])\n            {\n                auto iter = mp.begin();\n                iter++;\n                auto riter = mp.rbegin();\n                riter++;\n                int a = iter->second - iter->first + 1;\n                int b = riter->second - riter->first + 1;\n                if (a + b >= x)\n                {\n                    if (a >= x) ans -= (a + 1 - x);\n                    if (b >= x) ans -= (b + 1 - x);\n                    ans += (a + b + 1) - x;\n                }\n            }\n        }\n        return ans;\n    }\n\n    void rmonelen(int l)\n    {\n        cnt[l]--;\n        if (cnt[l] == 0) cnt.erase(l);\n    }\n\n    void insert(int a1, int b1)\n    {\n        if (b1 < a1) return;\n        mp[a1] = b1;\n        cnt[b1 - a1 + 1]++;\n    }\n\n    void rmIter(map<int, int>::iterator& it)\n    {\n        int l = it->second + 1 - it->first;\n        rmonelen(l);\n        mp.erase(it);\n    }\n\n    void change(int x)\n    {\n        auto iter = mp.upper_bound(x);\n        iter--;\n        int a = iter->first;\n        int b = iter->second;\n        auto pre = prev(iter);\n        auto suc = std::next(iter);\n\n        rmIter(iter);\n\n        int x1 = x;\n        int y1 = x;\n        if (a <= x - 1)\n        {\n            insert(a, x - 1);\n        } \n        else if (pre->second + 1 == x)\n        {\n            x1 = pre->first;\n            rmIter(pre);\n        }\n        \n        if (b >= x + 1)\n        {\n            insert(x + 1, b);\n        } \n        else if (suc->first == x + 1)\n        {\n            y1 = suc->second;\n            rmIter(suc);\n        }\n\n        insert(x1, y1);\n    }\n    \n    void Init()\n    {\n        int i = 0;\n        while (i < n)\n        {\n            int l = 0;\n            int x = i;\n            int pre = dp[x];\n\n            i++;\n            if (i >= n || dp[i] == pre)\n            {\n                insert(x, x);\n                continue;\n            }\n            \n            while (i < n && dp[i] != pre)\n            {\n                pre = dp[i];\n                i++;\n            }\n            insert(x, i - 1);\n        }\n    }\n\n    vector<int> numberOfAlternatingGroups(vector<int>& colors, vector<vector<int>>& qs) {\n        mp[INT_MIN] = INT_MIN;\n        mp[INT_MAX] = INT_MAX;\n        n = colors.size();\n        dp = colors;\n        Init();\n        \n        vector<int> ans;\n        for (auto& q : qs)\n        {\n            if (q[0] == 1)\n            {\n                ans.push_back(count(q[1]));\n            }\n            else \n            {\n                int x = q[1];\n                int v = q[2];\n                if (dp[x] == v) continue;\n                dp[x] = v;\n                change(x);\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']