100 LOC solution
Intuition\n Describe your first thoughts on how to solve this problem. \n- We have some non-overlapping maximal color-alternating segments.\n- By knowing the le
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- We have some non-overlapping maximal color-alternating segments.\n- By knowing the length and count of maximal color-alternating segments, we can answer each $$[1, size_i]$$ query in $$O(\\sqrt{N})$$ time, because there can be at most $$\\sqrt{2N}$$ different lengths of segments.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Put all segments in a set container.\n- Whenever there is change to the set container, update the segment-length counter correspondingly. \n\n# Implementation Details\n- Create a `diff[idx]` array that indicates if `color[idx-1]` and `color[idx]` alternates, then our interested "color-alternating segments" becomes "continuous `diff[idx] = true`".\n- For the simplicity of segment tree implementation, we repeat the `diff` array once, thus\n  - all the segments crossing $$idx = 0$$ would be handled per normal with $$segment_{left} <= N, segment_{right} > N$$\n  - we only count segments that starts within $[1, N]$, to prevent double counting the repeated segments\n- Make sure the segments are semi open.\n\n# Complexity\n- Time complexity:\n$$T_{initialize} + T_{changeColor} + T_{count} = O(N\\log N) + O(Q\\log N) + O(Q\\sqrt{N}) = O(N\\log N + Q\\sqrt{N})$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ --> \n\n- Space complexity:\n$$ S_{setContainer} + S_{mapContainer} + S_{diffArray} = O(N) + O(\\sqrt{N}) + O(N) = O(N) $$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\ntypedef pair<int, int> Pii;\nclass Segs{\n    public:\n        Segs(int n) : N(n) {}\n        int calc(int n){\n            if(segs.size() == 1 && *segs.begin() == make_pair(0, N*2))\n                return N;\n            int ans = 0;\n            for(auto p:cnt)\n                ans += p.second * max(p.first - n + 1, 0);\n            return ans;\n        }\n        void pop(set<Pii>::iterator it){\n            int len = it->second - it->first;\n            if(it->first && it->first <= N && --cnt[len] == 0)\n                cnt.erase(len);\n            segs.erase(it);\n        }\n        void insert(Pii p){\n            emplace(p.first, p.second);\n        }\n        void emplace(int l, int r){\n            int len = r - l;\n            if(l && l<=N)\n                cnt[len]++;\n            segs.emplace(l, r);\n        }\n        void add(int v){\n            emplace(v, v+1);\n            merge(v, v+1);\n            emplace(v+N, v+N+1);\n            merge(v+N, v+N+1);\n        }\n        void minus(int v){\n            remove(v);\n            remove(v+N);\n        }\n        void merge(int l, int r){\n            Pii key(l, 0);\n            auto it = segs.lower_bound(key);\n            auto rs = next(it);\n            if(rs != segs.end() && rs->first == it->second){\n                int ll = it->first, rr = rs->second;\n                pop(rs);\n                pop(segs.lower_bound(key));\n                emplace(ll, rr);\n            }\n            it = segs.lower_bound(key);\n            if(it != segs.begin() && prev(it)->second == it->first){\n                auto ls = prev(it);\n                int ll = ls->first, rr = it->second;\n                pop(ls);\n                pop(segs.lower_bound(key));\n                emplace(ll, rr);\n            }\n        }\n        void remove(int v){\n            auto it = prev(segs.upper_bound(make_pair(v+1, 0)));\n            Pii s[2] = {make_pair(it->first, v), make_pair(v+1, it->second)};\n            pop(it);\n            for(auto p:s)\n                if(p.first != p.second)\n                    insert(p);\n        }\n    private:\n        set<Pii> segs;\n        map<int, int> cnt;\n        int N;\n};\nclass Solution {\npublic:\n    void toggleDiff(int idx, vector<int> &diff, Segs &s){\n        if(diff[idx])\n            s.minus(idx);\n        else\n            s.add(idx);\n        diff[idx] ^= 1;\n    }\n    vector<int> numberOfAlternatingGroups(vector<int>& colors, vector<vector<int>>& queries) {\n        int N = colors.size();;\n        Segs segs(N);\n        vector<int> diff(N);\n        for(int i=0; i<N; i++)\n            if(colors[i] != colors[(i+N-1)%N]){\n                diff[i] = 1;\n                segs.add(i);\n            }\n        vector<int> ans;\n        for(auto cmd:queries){\n            if(cmd[0] == 1){\n                ans.push_back(segs.calc(cmd[1]-1));\n            } else if(colors[cmd[1]] != cmd[2]){\n                colors[cmd[1]] = cmd[2];\n                toggleDiff(cmd[1], diff, segs);\n                toggleDiff((cmd[1]+1)%N, diff, segs);\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']