C++ || Intution to solve O(Nlogn) solution || Not easy solution
Intuition\nKeep alternating groups in a set. Do not worry about the group which goes through (n-1)->(0). Just consider it a straight line and keep groups. (only
# Intuition\nKeep alternating groups in a set. Do not worry about the group which goes through (n-1)->(0). Just consider it a straight line and keep groups. (only maximal groups). Remember also keep groups of size 1,2 etc.\n\nNow maintain a segmentree tree/fenwick tree to maintain a datastructure which can maintain fequency of size of alternating groups. And give query(l,r) returns groups of size l\nIt would be something like\n```\nfreq[l]+2*freq[l+1]+3*freq[l+1]...\n```\n\nNow for updage query, one of the three things can happen. \na) break a chain into two \nb) merge two chains\nc) change length of at max one chains\n\nHandle that in O(logn) and update the frequency.\n\nCorner cases:\n- Now while answering query. Check size of first and last set. and see if they form a chain. Update answer accordingly.\n- If whole circle is a group, \n    - If first and last element are different answer is n\n    - otherwise normal logic applies.\n\n\n# Approach\n\n# Complexity\n- Time complexity:\nO(((n+q)logn)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass SegmentTree {\npublic:\n    SegmentTree(int n) : n(n) {\n        sum1.assign(2 * n, 0);\n        sum2.assign(2 * n, 0);\n    }\n\n    void update(int idx, int delta) {\n        if(idx == 0)\n            return;\n        int diff1 = delta;\n        int diff2 = delta * idx;\n\n        for (int i = idx + n; i > 0; i /= 2) {\n            sum1[i] += diff1;\n            sum2[i] += diff2;\n        }\n    }\n\n    int querySum1(int left, int right) {\n        return query(sum1, left, right);\n    }\n\n    int querySum2(int left, int right) {\n        return query(sum2, left, right);\n    }\n\n    int computeResult(int l, int r) {\n        int sum1Val = querySum1(l, r);\n        int sum2Val = querySum2(l, r);\n        return sum2Val - max(l-1,0) * sum1Val;\n    }\n\nprivate:\n    int n;\n    vector<int> sum1, sum2;\n\n    int querySingle(const vector<int>& tree, int idx) {\n        return tree[idx + n];\n    }\n\n    int query(const vector<int>& tree, int left, int right) {\n        int res = 0;\n        for (left += n, right += n + 1; left < right; left /= 2, right /= 2) {\n            if (left % 2 == 1) res += tree[left++];\n            if (right % 2 == 1) res += tree[--right];\n        }\n        return res;\n    }\n};\n\n\nclass Solution {\n\n    \n\npublic:\n    vector<int> numberOfAlternatingGroups(vector<int>& colors, vector<vector<int>>& queries) {\n        int n = colors.size();\n        set<pair<int, int>> groups;\n        map<int, int> sizeCounts;\n\n        SegmentTree st(n+1);\n        // Function to update the set of alternating groups\n        auto updateGroups = [&](int l, int r, bool adding) {\n            if(l<=r) {\n                int size = r - l + 1;\n                if (adding) {\n                    groups.insert({l, r});\n                    st.update(size,1);\n                } else {\n                    groups.erase({l, r});\n                    st.update(size,-1);\n                }\n            }\n        };\n\n\n        auto isAlternate = [&](int i) {\n            return colors[i] != colors[(i - 1 + n) % n];\n        };\n        // Initialize the groups\n        int start = 0;\n        while (start < n) {\n            int end = start;\n            while (end+1<=n-1 && isAlternate(end+1)) {\n                end = (end + 1) % n;\n            }\n            updateGroups(start, end, true);\n            start = end+1;\n        }\n\n        vector<int> result;\n        for (auto& query : queries) {\n            if (query[0] == 1) {\n                int size = query[1];\n                if(groups.size()==1) {\n                    if(colors[n-1]!= colors[0])\n                        result.push_back(n);\n                    else\n                        result.push_back(n-size+1);\n                    continue;\n                }         \n                int ans = st.computeResult(size,n);\n                if(colors[n-1]!= colors[0]) {\n                    auto it = groups.begin();\n                    int sz = it->second-it->first+1;\n                    if(sz>=size) {\n                        ans -= sz-size+1;\n                    }\n                    it = groups.end();\n                    it--;\n                    int sz2 = it->second-it->first+1;\n                    if(sz2>=size) {\n                        ans -= sz2-size+1;\n                    }\n                    sz+=sz2;\n                    if(sz>=size) {\n                        ans += sz-size+1;\n                    }\n                }\n                result.push_back(ans);\n                continue;\n            }  \n            int index = query[1];\n            int newColor = query[2];\n            if (colors[index] == newColor) \n                continue;\n            colors[index] = newColor;\n            auto it = groups.lower_bound({index+1, index+1});\n            it--;\n            if (it != groups.end() && it->first <= index) {\n                int l = it->first;\n                int r = it->second;\n                if(l==index && r==index) {\n                    int l2 = l;\n                    int r2 = r;\n\n                    if(it!=groups.begin()) {\n                        it--;\n                        l2=it->first;\n                        assert(it->second+1==index);\n                        it++;\n                    }\n\n                    it++;\n                    if(it!=groups.end()) {\n                        r2=it->second;\n                        assert(it->first-1==index);\n                    }\n                    updateGroups(l, r, false);\n                    updateGroups(l2, r2, true);\n                    if(l2!=l) {\n                        updateGroups(l2, index-1, false);\n                    }\n                    if(r2!=r) {\n                        updateGroups(index+1, r2, false);\n                    }\n                    continue;\n                }\n\n                if(l==index && it!=groups.begin()) {\n                    it--;\n                    int l2 = it->first;\n                    int r2 = it->second;\n                    if(r2+1 == index) {\n                        updateGroups(l2, r2, false);\n                        updateGroups(l2, r2+1, true);                    \n                    }\n                }\n                if(r==index){\n                    it++;\n                    if(it!=groups.end()) {\n                        int l2 = it->first;\n                        int r2 = it->second;\n                        if(index+1 == l2) {\n                            updateGroups(l2, r2, false);\n                            updateGroups(l2-1, r2, true);                    \n                        }\n                    }\n                }\n                updateGroups(l, r, false);\n                updateGroups(l, index-1, true);\n                updateGroups(index+1, r, true);\n\n                it = groups.lower_bound({index, index});\n                if(it==groups.end() || it->first>index) {\n                    if(it==groups.begin()) \n                        updateGroups(index,index,true);\n                    else {\n                        it--;\n                        if(it->second<index)\n                            updateGroups(index,index,true);\n                    }\n                }\n            } else {\n                assert(false);\n            }            \n        }\n\n        return result;\n    }\n};\n\n```
['C++']