Video Explanation (Starting from brute force and optimising step by step)
Explanation\n\nClick here for the video\n\n# Code\n\n#define pii pair<int, int>\n#define F first\n#define S second\n \nstruct SegTree {\npublic:\n \n    SegTree
# Explanation\n\n[Click here for the video](https://youtu.be/vOy6pzPqC9I)\n\n# Code\n```\n#define pii pair<int, int>\n#define F first\n#define S second\n \nstruct SegTree {\npublic:\n \n    SegTree (int _n) : n (_n) {\n        tree_val.resize(4*n, 0);\n        tree_cnt.resize(4*n, 0);\n    }\n    \n    int query_sum (int x) {\n        return query_sum (x, n-1, 0, n-1, 0);\n    }\n    \n    int query_cnt (int x) {\n        return query_cnt (x, n-1, 0, n-1, 0);\n    }\n    \n    void update (int ind, int val) {\n        update (ind, val, 0, n-1, 0);\n    }\n \nprivate:\n    \n    vector<int> tree_val;\n    vector<int> tree_cnt;\n    int n;\n    \n    int query_sum (int x, int y, int l, int r, int i) {\n        if (r < x || l > y) return 0;\n        if (l >= x && r <= y) return tree_val[i];\n        \n        int m = (l+r) >> 1;\n        return (\n            query_sum (x, y, l, m, i*2+1) +\n            query_sum (x, y, m+1, r, i*2+2)\n        );\n    }\n    \n    int query_cnt (int x, int y, int l, int r, int i) {\n        if (r < x || l > y) return 0;\n        if (l >= x && r <= y) return tree_cnt[i];\n        \n        int m = (l+r) >> 1;\n        return (\n            query_cnt (x, y, l, m, i*2+1) +\n            query_cnt (x, y, m+1, r, i*2+2)\n        );\n    }\n    \n    void update (int ind, int val, int l, int r, int i) {\n        if (l == r) {\n            tree_cnt[i] += val;\n            tree_val[i] = tree_cnt[i]*l;\n            return;\n        }\n        \n        int m = (l+r) >> 1;\n        if (m >= ind) update (ind, val, l, m, i*2+1);\n        else update (ind, val, m+1, r, i*2+2);\n        \n        tree_val[i] = tree_val[i*2+1] + tree_val[i*2+2];\n        tree_cnt[i] = tree_cnt[i*2+1] + tree_cnt[i*2+2];\n    }\n};\n\nclass Solution {\n    \n    int n;\n    \n    int Count (int q, pii last, SegTree& tree) {\n        int sum = tree.query_sum(q);\n        int cnt = tree.query_cnt(q);\n        int ans = sum - (q-1)*cnt;\n                \n        int l = last.F, r = last.S;\n        if (l >= n || (r-l+1) < q) return ans;\n        \n        if (r >= n) {\n            int can = n-l;\n            int has = (r-l+1) - (q-1);\n            if (can < has) ans -= (has - can);\n        }\n        return ans;\n    }\n    \n    void Remove (pii val, set<pii>& all, SegTree& tree) {\n        all.erase (val);\n        if (val.F >= n) return;\n        \n        tree.update (val.S-val.F+1, -1);\n    }\n    \n    void Insert (pii val, set<pii>& all, SegTree& tree) {\n        all.insert (val);\n        if (val.F >= n) return;\n        \n        tree.update (val.S-val.F+1, 1);\n    }\n    \n    pii GroupContainingX (int ind, set<pii>& all) {\n        auto it = all.upper_bound({ind, -1});\n        if (it != all.begin()) {\n            auto prv = it;\n            prv --;\n            if (prv->S >= ind) it = prv;\n        }\n        return *it;\n    }\n    \n    void update (int ind, int val, set<pii>& all, vector<int>& arr, SegTree& tree) {\n        if (ind == 2*n-1 || arr[ind] == val) return;\n        arr[ind] = val;\n\n        pii with_ind = GroupContainingX (ind, all);\n        Remove (with_ind, all, tree);\n        int l = with_ind.F, r = with_ind.S;\n        \n        if (l < ind && r > ind) {\n            Insert ({l, ind-1}, all, tree);\n            Insert ({ind, ind}, all, tree);\n            Insert ({ind+1, r}, all, tree);\n            return;\n        }\n        \n        // r == ind || l == ind\n        if (l == ind && r != ind) Insert ({l+1, r}, all, tree);\n        if (r == ind && l != ind) Insert ({l, r-1}, all, tree);\n        \n        l = r = ind;\n        auto it = all.upper_bound({ind, -1});\n        \n        vector<pii> to_remove;\n        \n        auto lft = it, rgt = it;\n        while (lft != all.begin()) {\n            lft --;\n            if (arr[lft->S] == arr[l]) break;\n            \n            to_remove.push_back(*lft);\n            l = lft->F;\n        }\n        while (rgt != all.end()) {\n            if (arr[rgt->F] == arr[r]) break;\n            \n            to_remove.push_back(*rgt);\n            r = rgt->S;\n            rgt ++;\n        }\n        \n        for (auto i : to_remove) Remove (i, all, tree);\n        Insert ({l, r}, all, tree);\n    }\n    \npublic:\n    vector<int> numberOfAlternatingGroups(vector<int>& colors, vector<vector<int>>& queries) {\n        n = colors.size();\n        \n        vector<int> arr(2*n);\n        for (int j = 0; j < n; j ++) arr[j] = colors[j];\n        for (int j = n; j < 2*n; j ++) arr[j] = colors[j-n];\n        \n        SegTree tree(2*n);\n        \n        set<pii> all;\n        for (int j = 0; j < 2*n-1; j ++) {\n            int l = j, r = j+1;\n            while (r < 2*n-1 && arr[r] != arr[r-1]) r ++;\n            \n            Insert ({l, r-1}, all, tree);\n            j = r-1;\n        }\n        \n        vector<int> result;\n        for (auto q: queries) {   \n            if (q[0] == 1) {\n                result.push_back(Count(q[1], GroupContainingX (n, all), tree));\n                continue;\n            } \n            \n            int ind = q[1], val = q[2];\n            update (ind, val, all, arr, tree);\n            update (n+ind, val, all, arr, tree);\n        }\n        return result;\n    }\n};\n```
['C++']