Detailed explanation || Brute Force to Efficient || C++ Beginner Friendly
Intuition\nCredits : @twitch_tv_qiqi_impact mentioned brute force solution in python. I converted it into cpp and made it more efficient later using segment tre
# Intuition\nCredits : @twitch_tv_qiqi_impact mentioned brute force solution in python. I converted it into cpp and made it more efficient later using segment tree.\n\nWe have to do two ops: \n1. Update alternating groups and keep track of them efficiently\n2. Count number of alternating groups of size >= some value\n\nHigh level idea : We can keep track of alternating groups in a set of pairs, where first value in pair is the index where the group starts, and second value is the size of that group. We can keep track of group sizes in different array and do the second query using that array. \n\n# Brute Force Approach\nWe will have alt array other than original array, where alt[i] is 1 if (colors[i]!=colors[i+1]) else 0. (Note : i+1 also considers the wraparound here as the array is circular). \n\nUsing this alt array, we will store contiguous blocks of 1\'s of alt array in set st in format of pairs {starting index, size of block}. We will also have a ct array where ct[i]=no. of blocks of 1 of size i. \n\nNote that a contiguous block of 1s of size sz in alt array is actually an alternating group of size sz+1 in colors array.\n\nQuery 1: \nWe have to update colors[i]. Whenever colors[i] changes, alt[i] and alt[i-1] (again i-1 means considering wraparound) both flip their values (between 0 and 1). There are some cases when a bit flips in alt[i]:\n1. From 0 to 1: The current 1 can either be standalone, can merge into a previous group of 1s, into a next group of 1s or can merge into both. Handle those cases correctly and update in set and ct array.\n2. From 1 to 0: It can divide a group into two groups, or it can be a standalone 1. Handle cases correctly and update in set and ct array. \n\nQuery 2:\nWe have to find number of alternating groups of size sz. Let t>=sz, then number of alternating groups of size sz in group of size t = t-sz+1. So, in alt array, it is actually t-sz+2 if t is size of contiguous block of 1s (read the note again).\nIterate i from sz-1 to n in ct array, and add ct[i]*(i-sz+2) to answer. There are some edge cases to handle: \n1. Only one group of 1s of size n is there, then answer is simply n.\n2. If two groups of 1s are such that one is starting from 0 and other is ending at n-1, then remove their individual contributions from answer, and add their combined contribution.\n\n# Complexity\n- Time complexity: O( nlogn + q ( logn + \u221An ) ) //q is number of queries\n\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution {\npublic:\n\n    vector<int> alt,ct;\n\n    //set stores contiguous blocks of 1s in alt as \n    //{starting index, size of block}\n    set<pair<int,int>> st;\n    \n    //finds block of 1 which contains index\n    //if index==0 return {-1,-1}\n    pair<int,int> findGroup(int index){\n        auto it=st.upper_bound({index,100000});\n        if(it==st.begin()) return {-1,-1};\n        it--;\n        if(it->first>index || it->first+it->second-1<index) return {-1,-1};\n        return *it;\n    }\n    \n    //flips alt value at index\n    void flip(int index){\n        alt[index]=1-alt[index];\n\n        //cases when new 1 comes\n        if(alt[index]==1){\n            pair<int,int> g1=findGroup(index-1),g2=findGroup(index+1),x={-1,-1};\n            if(g1==x){\n                if(g2==x){\n                    st.insert({index,1});\n                    ct[1]++;\n                }\n                else{\n                    st.erase(g2);\n                    ct[g2.second]--;\n                    st.insert({index,g2.second+1});\n                    ct[g2.second+1]++;\n                }\n            }\n            else{\n                if(g2==x){\n                    st.erase(g1);\n                    ct[g1.second]--;\n                    st.insert({g1.first,g1.second+1});\n                    ct[g1.second+1]++;\n                }\n                else{\n                    st.erase(g1);\n                    st.erase(g2);\n                    ct[g1.second]--;\n                    ct[g2.second]--;\n                    st.insert({g1.first,g1.second+g2.second+1});\n                    ct[g1.second+g2.second+1]++;\n                }\n            }\n        }\n        //cases when 1 is flipped into 0\n        else{\n            pair<int,int> g=findGroup(index);\n            st.erase(g);\n            ct[g.second]--;\n            if(g.second!=1){\n                if(g.first<index){\n                    st.insert({g.first,index-g.first});\n                    ct[index-g.first]++;\n                }\n                if(g.first+g.second-1>index){\n                    st.insert({index+1,g.first+g.second-(index+1)});\n                    ct[g.first+g.second-(index+1)]++;\n                }\n            }\n        }\n    }\n    \n    //finds alt groups of size val\n    int altGroups(int val){\n        int n=ct.size()-1,ans=0;\n        //edge case 2\n        if(st.size()==1 && st.begin()->second==n) return n;\n        \n        for(int i=val-1;i<=n;++i){\n            ans+=ct[i]*(i-val+2);\n        }\n\n        //edge case 2\n        if(st.size()>=2 && alt[0]==1 && alt[n-1]==1){\n            pair<int,int> g1=*st.begin(),g2=*(--st.end());\n            if(g1.second>=val-1) ans-=g1.second-val+2;\n            if(g2.second>=val-1) ans-=g2.second-val+2;\n            if(g1.second+g2.second>=val-1) ans+=g1.second+g2.second-val+2;\n        }\n        return ans;\n    }\n    \n    vector<int> numberOfAlternatingGroups(vector<int>& colors, vector<vector<int>>& queries) {\n        int n=colors.size();\n        ct.resize(n+1);\n\n        for(int i=0;i<n;++i){\n            alt.push_back(colors[i]!=colors[(i+1)%n]);\n        }\n        //track blocks of 1 in set and their sizes in ct\n        for(int i=0;i<n;++i){\n            if(alt[i]==0) continue;\n            int j=i;\n            while(j<n && alt[j]==1){\n                j++;\n            }\n            st.insert({i,j-i});\n            ct[j-i]++;\n            i=j;\n        }\n\n        vector<int> ans;\n        for(auto& q:queries){\n            if(q.size()==2){\n                ans.push_back(altGroups(q[1]));\n            }\n            else{\n                //don\'t do anything if value at colors is same\n                if(colors[q[1]]==q[2]) continue;\n                colors[q[1]]=q[2];\n                //flip current and preious indices in alt\n                flip(q[1]);\n                flip((q[1]-1+n)%n);\n            }\n        }\n        return ans;\n    }\n};\n```\n\n# Efficient Approach\nWe can see that the most time taking operation is query 2, which takes \u221An complexity. Even though brute force approach passes the test cases, we can make it better. If we look carefully at query 2, we are taking :\nsummation ( ct[i]*(i+2-sz)) for i=(sz-1 to n) for finding number of alternating segments of size sz. We can use segment tree to query this value in logn, by expanding the equation as ct[i]\\*(i+2) - ct[i]\\*sz.  \n\nWe can maintain two segment trees, one of which stores ct[i]*(i+2) and another stores ct[i], and then keeps their sums, which we can query efficiently. \n\n# Complexity\n- Time complexity: O( nlogn + q (logn) )\n\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    //ct and seg are two segment trees\n    vector<int> alt,ct,seg;\n    set<pair<int,int>> st;\n    int n;\n    \n    pair<int,int> findGroup(int index){\n        auto it=st.upper_bound({index,100000});\n        if(it==st.begin()) return {-1,-1};\n        it--;\n        if(it->first>index || it->first+it->second-1<index) return {-1,-1};\n        return *it;\n    }\n    \n    //updates an index of both ct and seg\n    void update(int index, int val){\n        for(seg[index+n+1]+=val*(index+2),ct[index+n+1]+=val,index+=n+1;index>1;index>>=1){\n            seg[index>>1]=seg[index]+seg[index^1];\n            ct[index>>1]=ct[index]+ct[index^1];\n        }\n    }\n    \n    //returns sum of [l,r] in {seg,ct}\n    pair<int,int> query(int l, int r){\n        r++;\n        int x=0,y=0;\n        for(l+=n+1,r+=n+1;l<r;l>>=1,r>>=1){\n            if(l&1){\n                x+=seg[l];\n                y+=ct[l++];\n            }\n            if(r&1){\n                x+=seg[r-1];\n                y+=ct[--r];\n            }\n        }\n        return {x,y};\n    }\n    \n    void flip(int index){\n        alt[index]=1-alt[index];\n        if(alt[index]==1){\n            pair<int,int> g1=findGroup(index-1),g2=findGroup(index+1),x={-1,-1};\n            if(g1==x){\n                if(g2==x){\n                    st.insert({index,1});\n                    update(1,-1);\n                }\n                else{\n                    st.erase(g2);\n                    update(g2.second,-1);\n                    st.insert({index,g2.second+1});\n                    update(g2.second+1,1);\n                }\n            }\n            else{\n                if(g2==x){\n                    st.erase(g1);\n                    update(g1.second,-1);\n                    st.insert({g1.first,g1.second+1});\n                    update(g1.second+1,1);\n                }\n                else{\n                    st.erase(g1);\n                    st.erase(g2);\n                    update(g1.second,-1);\n                    update(g2.second,-1);\n                    st.insert({g1.first,g1.second+g2.second+1});\n                    update(g1.second+g2.second+1,1);\n                }\n            }\n        }\n        else{\n            pair<int,int> g=findGroup(index);\n            st.erase(g);\n            update(g.second,-1);\n            if(g.second!=1){\n                if(g.first<index){\n                    st.insert({g.first,index-g.first});\n                    update(index-g.first,1);\n                }\n                if(g.first+g.second-1>index){\n                    st.insert({index+1,g.first+g.second-(index+1)});\n                    update(g.first+g.second-(index+1),1);\n                }\n            }\n        }\n    }\n    \n    int altGroups(int val){\n        if(st.size()==1 && st.begin()->second==n) return n;\n        \n        //query in logn instead of \u221An\n        pair<int,int> ret=query(val-1,n);\n        int ans=ret.first-(ret.second*val);\n\n        if(st.size()>=2 && alt[0]==1 && alt[n-1]==1){\n            pair<int,int> g1=*st.begin(),g2=*(--st.end());\n            if(g1.second>=val-1) ans-=g1.second-val+2;\n            if(g2.second>=val-1) ans-=g2.second-val+2;\n            if(g1.second+g2.second>=val-1) ans+=g1.second+g2.second-val+2;\n        }\n        return ans;\n    }\n    \n    vector<int> numberOfAlternatingGroups(vector<int>& colors, vector<vector<int>>& queries) {\n        n=colors.size();\n        ct.resize(2*(n+1));\n        seg.resize(2*(n+1));\n        for(int i=0;i<n;++i){\n            alt.push_back(colors[i]!=colors[(i+1)%n]);\n        }\n        for(int i=0;i<n;++i){\n            if(alt[i]==0) continue;\n            int j=i;\n            while(j<n && alt[j]==1){\n                j++;\n            }\n            st.insert({i,j-i});\n            update(j-i,1);\n            i=j;\n        }\n        vector<int> ans;\n        for(auto& q:queries){\n            if(q.size()==2){\n                ans.push_back(altGroups(q[1]));\n            }\n            else{\n                if(colors[q[1]]==q[2]) continue;\n                colors[q[1]]=q[2];\n                flip(q[1]);\n                flip((q[1]-1+n)%n);\n            }\n        }\n        return ans;\n    }\n};\n```
['Array', 'Binary Indexed Tree', 'Segment Tree', 'Ordered Map', 'C++']