Easy C++
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass SegTree {\n    vector<pair<int, int>> st;  // from left to right: sum of index*value, sum of values\n    vector<int> arr;\n\n   public:\n    SegTree(vector<int> &a, int maxValue) {\n        st.resize(4 * maxValue);\n        arr.resize(maxValue + 1, 0);\n        for (auto &x : a)\n            arr[x]++;\n        a = arr;\n        build(0, 0, arr.size() - 1);\n    }\n\n    pair<int, int> query(int groupSizeFrom) {\n        return this->query(groupSizeFrom, arr.size() - 1, 0, 0, arr.size() - 1);\n    }\n\n    void update(int groupSize, int newGroupCount) {\n        arr[groupSize] = newGroupCount;\n        this->update(groupSize, 0, 0, arr.size() - 1);\n    }\n\n   private:\n    void build(int si, int sl, int sr) {\n        // sl...sr in arr is represented by this node\n        if (sl == sr) {\n            int index = sl;\n            st[si] = {arr[index] * index, arr[index]};  // index*value, value\n            return;\n        }\n        int mid = (sl + sr) / 2;\n        build(si * 2 + 1, sl, mid);\n        build(si * 2 + 2, mid + 1, sr);\n        st[si] = {st[si * 2 + 1].first + st[si * 2 + 2].first,\n                  st[si * 2 + 1].second + st[si * 2 + 2].second};\n    }\n\n    void update(int index, int si, int sl, int sr) {\n        // assuming arr[index] was updated before this call\n        if (sl == sr) {\n            st[si] = {arr[index] * index, arr[index]};  // index*value, value\n            return;\n        }\n        int mid = (sl + sr) / 2;\n        if (index <= mid)\n            update(index, si * 2 + 1, sl, mid);\n        else\n            update(index, si * 2 + 2, mid + 1, sr);\n        st[si] = {st[si * 2 + 1].first + st[si * 2 + 2].first,\n                  st[si * 2 + 1].second + st[si * 2 + 2].second};\n    }\n\n    pair<int, int> query(int l, int r, int si, int sl, int sr) {\n        if (sl > r || sr < l)\n            return {0, 0};\n        if (sl >= l && sr <= r)\n            return st[si];\n        int mid = (sl + sr) / 2;\n        auto [leftSum, leftValueSum] = query(l, r, si * 2 + 1, sl, mid);\n        auto [rightSum, rightValueSum] = query(l, r, si * 2 + 2, mid + 1, sr);\n        return {leftSum + rightSum, leftValueSum + rightValueSum};\n    }\n};\n\nclass Solution {\n    int findSize(int left, int right, int &n) {\n        if (right >= left)\n            return right - left + 1;\n        return n - left + right + 1;\n        return ((right - left + 1) % n + n) % n;\n    }\n    int findSize(const pair<int, int> &p, int &n) {\n        return findSize(p.first, p.second, n);\n    }\n\n   public:\n    vector<int> numberOfAlternatingGroups(vector<int> &colors, vector<vector<int>> &queries) {\n        set<pair<int, int>> groups;\n        vector<int> sizes;\n        int n = colors.size();\n        // forming groups\n        {\n            int start = -1;\n            for (int i = 0; i < n; i++) {\n                if (colors[i] == colors[((i - 1) % n + n) % n]) {\n                    start = i;\n                    break;\n                }\n            }\n            if (start == -1) {\n                sizes.push_back(findSize(0, n - 1, n));\n                groups.insert({0, n - 1});\n            } else {\n                int cur = (start + 1) % n;\n                while (cur != start && colors[cur] != colors[(cur + n - 1) % n])\n                    cur = (cur + 1) % n;\n                groups.insert({start, (cur - 1 + n) % n});\n                sizes.push_back(findSize(start, (cur - 1 + n) % n, n));\n\n                while (cur != start) {\n                    int next = (cur + 1) % n;\n                    while (next != start && colors[next] != colors[(next - 1 + n) % n])\n                        next = (next + 1) % n;\n                    // cur....next-1 is one group\n                    groups.insert({cur, (next - 1 + n) % n});\n                    sizes.push_back(findSize(cur, (next - 1 + n) % n, n));\n                    cur = next;\n                }\n            }\n        }\n        // create segment tree for querying\n        // max group size is n\n        SegTree segTree(sizes, n);\n        vector<int> sizesCount = sizes;  // sizes was modified inside the segTree to contain the sizeCounters\n        vector<int> ans;\n        vector<pair<int, int>> toRemove;  // clear after every query\n        vector<pair<int, int>> toAdd;     // clear after every query\n\n        auto removeSegment = [&](const pair<int, int> &segment) {\n            int segmentSize = findSize(segment, n);\n            int currentCount = sizesCount[segmentSize];\n            sizesCount[segmentSize]--;\n            segTree.update(segmentSize, sizesCount[segmentSize]);\n            toRemove.push_back(segment);\n        };\n\n        auto addSegment = [&](const pair<int, int> &segment) {\n            int segmentSize = findSize(segment, n);\n            int currentCount = sizesCount[segmentSize];\n            sizesCount[segmentSize]++;\n            segTree.update(segmentSize, sizesCount[segmentSize]);\n            toAdd.push_back(segment);\n        };\n\n        auto getPreviousSegment = [&](const set<pair<int, int>>::iterator &it) -> set<pair<int, int>>::iterator {\n            if (it == groups.begin())\n                return --groups.end();\n            auto previousIterator = it;\n            previousIterator--;\n            return previousIterator;\n        };\n\n        auto getNextSegment = [&](const set<pair<int, int>>::iterator &it) -> set<pair<int, int>>::iterator {\n            auto nextIterator = it;\n            nextIterator++;\n            if (nextIterator == groups.end())\n                nextIterator = groups.begin();\n            return nextIterator;\n        };\n\n        for (auto &query : queries) {\n            int queryType = query[0];\n            if (queryType == 1) {\n                int queryGroupSize = query[1];\n                if (groups.size() == 1) {\n                    auto &[groupLeft, groupRight] = *groups.begin();\n                    if (colors[groupLeft] != colors[groupRight]) {\n                        // special case, only one single group is present and the array itself is one whole alternating wheel with no specific starting point\n                        // here, the answer would be the number of subarrays in circular array of size queryGroupSize\n                        ans.push_back(n);  // because we can take any point as the starting point\n                        continue;\n                    }\n                }\n                // ans = sum of groupSize*countOfThisGroupSize - numGroups * queryGroupSize + numGroups where groupSize >= queryGroupSize\n                auto [sizeCountSum, numGroups] = segTree.query(queryGroupSize);\n                ans.push_back(sizeCountSum - numGroups * queryGroupSize + numGroups);\n            } else {\n                int index = query[1], color = query[2];\n                if (colors[index] == color)\n                    continue;\n\n                // step1: find the segment containing this index\n                auto currentSegment = groups.upper_bound(make_pair(index, INT_MAX));\n                currentSegment = getPreviousSegment(currentSegment);\n\n                // step2: break this segment down. all segments in the groups set are continous.\n                removeSegment(*currentSegment);\n                auto &[groupLeft, groupRight] = *currentSegment;\n\n                // special case when there is only one segment and it is already a full wheel with all alternating colors\n                if (groups.size() == 1 && colors[groupLeft] != colors[groupRight]) {\n                    // in this case, no matter where we flip the bit. it will always break into two parts instead of the usual three\n                    // 1010101010 --->  10101 1 1010\n                    //      ^           >---- - --->\n                    addSegment({index, index});\n                    addSegment({(index + 1) % n, (index - 1 + n) % n});\n                } else if (groupLeft == groupRight) {\n                    // only one element in segment. This will connect the left and right segments\n                    auto previousSegment = getPreviousSegment(currentSegment);\n                    auto nextSegment = getNextSegment(currentSegment);\n                    int currentIndex = groupLeft;\n                    if (*previousSegment == *nextSegment) {\n                        // there are only two groups available out of which the current group contains only 1 element. hence it will form 1 group of all elements\n                        // 1010101   1\n                        removeSegment(*previousSegment);\n                        addSegment({previousSegment->first, currentIndex});\n                    } else {\n                        // more than two other segments, hence we can remove both of them\n                        removeSegment(*previousSegment);\n                        removeSegment(*nextSegment);\n                        addSegment({previousSegment->first, nextSegment->second});\n                    }\n                } else if (index != groupLeft && index != groupRight) {\n                    // the position where the color was flipped was in between an existing group. hence this group will divide into three parts\n                    addSegment(make_pair(groupLeft, (index - 1 + n) % n));\n                    addSegment(make_pair(index, index));\n                    addSegment(make_pair((index + 1) % n, groupRight));\n                } else if (index == groupLeft) {\n                    // this means we go from 010 01010 to 0101 1010\n                    //                           ^\n                    auto previousSegment = getPreviousSegment(currentSegment);\n                    if (*previousSegment == *currentSegment) {  // this would only happen if there are only one segment available and we are changing the extreme point\n                        if (colors[groupLeft] == colors[groupRight]) {\n                            // the segment will just shift start and end points\n                            // 0 101010  to // 110101 0\n                            // s      e        es\n                            addSegment({(index + 1) % n, index});\n                        } else {\n                            // 0 10101  to // 1 10101\n                            // s     e        - -----\n                            addSegment({groupLeft, index});  // index == groupLeft, so segment containing only one element\n                            // now, after breaking, the current segment will be from groupLeft to index-1\n                            addSegment({(index + 1) % n, groupRight});\n                        }\n                    } else {\n                        // previousSegment will be extended\n                        // 10101 10101  --->  101010 0101\n                        //       ^                 ^\n                        \n                        removeSegment(*previousSegment);\n                        addSegment({previousSegment->first, index});\n                        // now, after breaking the second segment will be from index+1 to groupRight\n                        addSegment({(index + 1) % n, groupRight});\n                    }\n                } else {\n                    // index is at the rightmost end of the segment\n                    // this means we go from 010 01010 to 0101 1010\n                    //                         ^\n                    auto nextSegment = getNextSegment(currentSegment);\n                    if (*nextSegment == *currentSegment) {  // this would only happen if there are only one segment available and we are changing the extreme point\n                        if (colors[groupLeft] == colors[groupRight]) {\n                            // the segment will just shift start and end points\n                            // 010101 0  to // 010101 1\n                            // s      e             e s\n                            addSegment({index, (index - 1 + n) % n});\n                        } else {\n                            addSegment({index, groupRight});  // index == groupRight, so segment containing only one element\n                            // now, after breaking, the current segment will be from groupLeft to index-1\n                            addSegment({groupLeft, (index - 1 + n) % n});\n                        }\n                    } else {\n                        // nextSegment will be extended\n                        removeSegment(*nextSegment);\n                        addSegment({index, nextSegment->second});\n                        // now, after breaking, the current segment will be from groupLeft to index-1\n                        addSegment({groupLeft, (index - 1 + n) % n});\n                    }\n                }\n\n                // After changing of segments is done, remove and add the required segments to the groups set\n                for (auto &removeSegment : toRemove) {\n                    groups.erase(removeSegment);\n                }\n                for (auto &addSegment : toAdd) {\n                    groups.insert(addSegment);\n                }\n                toRemove.clear();\n                toAdd.clear();\n\n                // color is flipped for index\n                colors[index] = color;\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']