🥲🥲250 line code: DO NOT TRY THIS :(
Intuition\n Describe your first thoughts on how to solve this problem. \nintuition is segment tree ,but i am sure majority would skip to think of this intuition
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nintuition is segment tree ,but i am sure majority would skip to think of this intuition cause of implementing it will take multiple hours or may be days.But i tried this for fun..\n# Approach\n<!-- Describe your approach to solving the problem. -->\njust debug and run and recode, Kidding\n1. lets store longest aternating groups for every starting point in a segment tree and but last group happens to be the only group that touches boundary and has potential to cross boundary depending on a[0]&a[n-1] values (a[0]==a[n-1] not extendable else extendable ) but i will consider it upto index n-1 and store that information about last group in two variables for left and right of the last group,we wil handle only groups that are not crossing boundary i=n-1 including this last group in our segment tree but if last group happens to extendable beyond n-1 then we will not account for it in our segment tree.\n2. Now we should store every segment or groups as a pair of its left and right end in a map called *"groups"*.\n3. since we only need to find sum of groups with sizes >=k and count of such groups I modified my tree to include both in form of *pairs*\n4. you can refer to my code for clearity on how to perform most complex part of the code aka updating query for type 2. \n# Complexity\n- Time complexity:$$O(n+q*logn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\n    public:\n\n        class SegTree {\n            private: vector < pair < int, int > > tree;\n            int n;\n            public: SegTree(int n) {\n                this->n = n;\n                tree.assign(4 * n + 1, {0, 0});\n            }\n            void st_update(int i, int x) {\n                st_update(1, n, 1, i, x);\n            }\n            void st_update(int l, int r, int v, int i, int x) {\n                if (l == r) { // Leaf node update\n                    if (l == i)\n                    {\n                        tree[v].first += x;\n                        tree[v].second += (x < 0 ? -1 : 1);\n                    }\n                    return;\n                }\n                if (i < l || i > r) return; // Out of bounds, skip update\n                st_update(l, (l + r) / 2, 2 * v, i, x); // Update left child\n                st_update((l + r) / 2 + 1, r, 2 * v + 1, i, x); // Update right child\n                tree[v].first = tree[2 * v].first + tree[2 * v + 1].first;\n                tree[v].second = tree[2 * v].second + tree[2 * v + 1].second;\n            }\n            int st_rsq(int l, int r, int v, int i, int j) {\n                if (max(l, i) > min(r, j)) return 0; // No overlap\n                if (i <= l && r <= j) return tree[v].first; // Total overlap\n                // Partial overlap\n                return st_rsq(l, (l + r) / 2, 2 * v, i, j) + st_rsq((l + r) / 2 + 1, r, 2 * v + 1, i, j);\n            }\n            int st_rsq(int l, int r) {\n                return st_rsq(1, n, 1, l, r);\n            }\n            int st_cnt(int l, int r, int v, int i, int j) {\n                if (max(l, i) > min(r, j)) return 0; // No overlap\n                if (i <= l && r <= j) return tree[v].second; // Total overlap\n                return st_cnt(l, (l + r) / 2, 2 * v, i, j) + st_cnt((l + r) / 2 + 1, r, 2 * v + 1, i, j);\n            }\n            int st_cnt(int l, int r) {\n                return st_cnt(1, n, 1, l, r);\n            }\n        };\n\n    vector < int > numberOfAlternatingGroups(vector < int > & a, vector < vector < int >> & queries) {\n        int n = a.size(), q = queries.size();\n        map < int, pair < int, int >> groups;\n        SegTree * st = new SegTree(n);\n\n        int li = -1, ls = 0;\n        for (int i = 0; i < n; i++) {\n            int j = i;\n            while (j + 1 < n && a[j + 1] != a[j]) {\n                j++;\n            }\n            if (j == n - 1) {\n                li = i;\n                ls = n - 1 - li + 1;\n                groups[li] = { j, ls };\n                if (a[0] == a[n - 1]) st->st_update(j - i + 1, j - i + 1);\n            } else {\n                groups[i] = { j, j - i + 1 };\n                st->st_update(j - i + 1, j - i + 1);\n            }\n            i = j;\n        }\n\n        vector < int > res;\n        for (int i = 0; i < q; i++) {\n            if (queries[i][0] == 1) {\n                int k = queries[i][1];\n                int sum = st->st_rsq(k, n); // Sum of group sizes >= k\n                int cnt = st->st_cnt(k, n); // Count of groups with size >= k\n                int ans = sum - cnt * k + cnt; // Calculate the result for this query\n\n                if (a[0] != a[n - 1] && groups[0].second + ls >= k) ans += min(n - li, groups[0].second + ls - k + 1); //by last group if not in segment tree\n                res.push_back(ans);\n            } else {\n                if (a[queries[i][1]] == queries[i][2]) continue;\n                int indi = queries[i][1];\n                int colori = queries[i][2];\n                auto rg = groups.upper_bound(indi);\n                int pL = -1, pR = -1, L = -1, R = -1, Len = 0, nL = -1, nR = -1;\n                if (rg != groups.end()) {\n                    nL = rg->first;\n                    nR = rg->second.first;\n                }\n                if (rg != groups.begin()) {\n                    auto cur = --rg;\n                    L = cur->first;\n                    R = cur->second.first;\n                    Len = cur->second.second;\n                    if (cur != groups.begin()) {\n                        auto lf = --cur;\n                        pL = lf->first;\n                        pR = lf->second.first;\n                    }\n                }\n                update(pL,pR,L,R,Len,nL,nR,indi,colori,li,ls,n,a,st,groups);\n            }\n        }\n        return res;\n    }\n    void update(int pL,int pR,int L,int R,int Len,int nL,int nR,int indi,int colori,int &li,int &ls,int n,vector<int>&a,SegTree * &st,map<int,pair<int,int>>&groups){\n        vector < pair < int, int >> add, remove;\n                if (Len == 1) {\n                    if (pR != -1 && nR != -1) {\n                        if (a[pR] != colori && a[nL] != colori) {\n                            add.push_back({ pL, nR }); // Merge all three\n                            remove.push_back({ nL, nR });\n                            remove.push_back({ L, R });\n                            remove.push_back({ pL, pR });\n                            if (nR != n - 1 && indi == 0 && a[0] != colori) {\n                                remove.push_back({ li, n - 1 });\n                                add.push_back({ li, n - 1 });\n                            }\n                        } else if (a[pR] != colori) {\n                            add.push_back({ pL, R }); // Merge with previous\n                            remove.push_back({ L, R });\n                            remove.push_back({ pL, pR });\n                            if (R != n - 1 && indi == 0 && a[0] != colori) {\n                                remove.push_back({ li, n - 1 });\n                                add.push_back({ li, n - 1 });\n                            }\n                        } else if (a[nL] != colori) {\n                            add.push_back({ L, nR }); // Merge with next\n                            remove.push_back({ L, R });\n                            remove.push_back({ nL, nR });\n                            if (nR != n - 1 && indi == 0 && a[0] != colori) {\n                                remove.push_back({ li, n - 1 });\n                                add.push_back({ li, n - 1 });\n                            }\n                        }\n                    } else if (pR != -1) {\n                        if (a[pR] != colori) { // Merge with previous\n                            add.push_back({ pL, R });\n                            remove.push_back({ L, R });\n                            remove.push_back({ pL, pR });\n                            if (R != n - 1 && indi == 0 && a[0] != colori) {\n                                remove.push_back({ li, n - 1 });\n                                add.push_back({ li, n - 1 });\n                            }\n                        }\n                    } else if (nR != -1) {\n                        if (a[nL] != colori) { // Merge with next\n                            add.push_back({ L, nR });\n                            remove.push_back({ L, R });\n                            remove.push_back({ nL, nR });\n                            if (nR != n - 1 && indi == 0 && a[0] != colori) {\n                                remove.push_back({ li, n - 1 });\n                                add.push_back({ li, n - 1 });\n                            }\n                        }\n                    }\n                } else { // Current group has length > 1\n                    if (indi == L) { // Update at the left end of the group\n                        if (pR != -1) {\n                            add.push_back({ pL, pR + 1 });\n                            add.push_back({ L + 1, R });\n                            remove.push_back({ L, R });\n                            remove.push_back({ pL, pR });\n                            if (R != n - 1 && indi == 0 && a[0] != colori) {\n                                remove.push_back({ li, n - 1 });\n                                add.push_back({ li, n - 1 });\n                            }\n                        } else {\n                            add.push_back({ L + 1, R });\n                            add.push_back({ indi, indi });\n                            remove.push_back({ L, R });\n                            if (R != n - 1 && indi == 0 && a[0] != colori) {\n                                remove.push_back({ li, n - 1 });\n                                add.push_back({ li, n - 1 });\n                            }\n                        }\n                    } else if (indi == R) { // Update at the right end of the group\n                        if (nR != -1) {\n                            add.push_back({ nL - 1, nR });\n                            add.push_back({ L, R - 1 });\n                            remove.push_back({ L, R });\n                            remove.push_back({ nL, nR });\n                            if (nR != n - 1 && indi == 0 && a[0] != colori) {\n                                remove.push_back({ li, n - 1 });\n                                add.push_back({ li, n - 1 });\n                            }\n                        } else {\n                            add.push_back({ L, R - 1 });\n                            add.push_back({ indi, indi });\n                            remove.push_back({ L, R });\n                            if (R != n - 1 && indi == 0 && a[0] != colori) {\n                                remove.push_back({ li, n - 1 });\n                                add.push_back({ li, n - 1 });\n                            }\n                        }\n                    } else { // Update in the middle of the group\n                        add.push_back({ L, indi - 1 });\n                        add.push_back({ indi + 1, R });\n                        add.push_back({ indi, indi });\n                        remove.push_back({ L, R });\n                        if (R != n - 1 && indi == 0 && a[0] != colori) {\n                            remove.push_back({ li, n - 1 });\n                            add.push_back({ li, n - 1});\n                        }\n                    }\n                }\n\n                //(removal and addition of groups)\n                for (auto & r: remove) {\n                    if (groups.count(r.first)) {\n                        groups.erase(r.first);\n                        if (((a[n - 1] == a[0]) && (r.second == n - 1)) || (r.second < n - 1))\n                        {\n                            st->st_update(r.second - r.first + 1, -(r.second - r.first + 1));\n                        }\n                    }\n                }\n                for (auto & x: add) {\n                    groups[x.first] = {\n                        x.second,\n                        x.second - x.first + 1\n                    };\n                    if ((((a[n - 1] != a[0] && a[0] != colori && indi == 0) || (a[n - 1] == a[0] && indi && indi != n - 1) || (a[n - 1] != a[0] && indi == n - 1 && a[0] == colori)) && (x.second == n - 1)) || (x.second < n - 1))\n                    {\n                        st->st_update(x.second - x.first + 1, (x.second - x.first + 1));\n                    }\n                    if ((x.second == n - 1)) {\n                        li = x.first, ls = x.second - x.first + 1;\n                    }\n                }\n                //update new color\n                a[indi] = colori;\n    }\n};\n```
['Array', 'Binary Indexed Tree', 'C++']