Map and Set (No Segment Tree)
The idea is not that hard, but the implementation was very tricky for me.\n\n## Counter Map\nWe count how many groups of each size we have in a map cnt.\n\nSay 
The idea is not that hard, but the implementation was very tricky for me.\n\n## Counter Map\nWe count how many groups of each size we have in a map `cnt`.\n\nSay our map contains 3 groups of size 4 and 2 groups of size 5. If we want to count groups with size 4:\n- We search for, then iterate through groups of size 4 and larger.\n- We add 3 groups (count of groups of size 4).\n- Then we add 2 * (5 - 4 + 1) = 4 groups.\n\t- This is because a group of size 5 includes 2 groups of size 4.\n\nHow many different group sizes can we have in `cnt`? If there is just one group of each size, the answer is `sqrt(n)`.\n> Group sizes form an arithmetic progression from `3` to `m`, and `m * (m + 1) / 2 <= n`.  So `m` is `~sqrt(n)`.\n\n## Breaks Set\nWe store indices between two alternating groups in a set `breaks`. \n\nWe can store either first or second index of two tiles with the same color. \n> In the implementation below, we store the first index; it seems to simplify the code a bit.\n\nAs we change the color of a tile, we need to add and remove some "breaks".\n\nWhen we add or remove a break, we determine the size of old and new groups, and update the counter `cnt`.\n\nThis was particularly difficult to implement; to simplify, the code below handles cases when we have zero, one and two breaks separately.\n\n**C++**\n```cpp\nvoid add(int d, map<int, int> &cnt, int n) {\n    d = d < 0 ? d + n : d;\n    if (d > 2)\n        ++cnt[d];\n}\nvoid erase(int d, map<int, int> &cnt, int n) {\n    d = d < 0 ? d + n : d;\n    if (d > 2)\n        if (auto it = cnt.find(d); --it->second == 0)\n            cnt.erase(it);\n}\nvoid insert(int i, set<int> &breaks, map<int, int> &cnt, int n) {\n    if (breaks.empty())\n        cnt = map<int, int>{{n, 1}};\n    else if (breaks.size() == 1) {\n        int j = *begin(breaks);\n        cnt = map<int, int>{{abs(i - j), 1}};\n        ++cnt[n - abs(i - j)];            \n    }\n    else {\n        auto it3 = breaks.upper_bound(i);\n        if (it3 == end(breaks))\n            it3 = begin(breaks);\n        auto it1 = it3 == begin(breaks) ? prev(end(breaks)) : prev(it3);\n        erase(*it3 - *it1, cnt, n);\n        add(*it3 - i, cnt, n);\n        add(i - *it1, cnt, n);\n    }\n    breaks.insert(i);\n}\nvoid erase(int i, set<int> &breaks, map<int, int> &cnt, int n) {\n    auto it2 = breaks.find(i);\n    if (breaks.size() == 1)\n        cnt = map<int, int>{{2 * n, 1}};\n    else if (breaks.size() == 2)\n        cnt = map<int, int>{{n, 1}};\n    else {\n        auto it1 = it2 == begin(breaks) ? prev(end(breaks)) : prev(it2);\n        auto it3 = next(it2) == end(breaks) ? begin(breaks) : next(it2);\n        erase(*it2 - *it1, cnt, n);\n        erase(*it3 - *it2, cnt, n);\n        add(*it3 - *it1, cnt, n);\n    }\n    breaks.erase(it2);\n}\nvector<int> numberOfAlternatingGroups(vector<int>& colors, vector<vector<int>>& queries) {\n    int n = colors.size();    \n    set<int> breaks;\n    map<int, int> cnt = {{2 * n, 1}};         \n    for (int i = 0; i < n; ++i)\n        if (colors[i] == colors[(i + 1) % n])\n            insert(i, breaks, cnt, n);\n    vector<int> res;\n    for (const auto &q : queries) {\n        if (q[0] == 1) {\n            int count = 0;\n            for (auto it = cnt.lower_bound(q[1]); it != end(cnt); ++it)\n                count += it->second * (it->first - q[1] + 1);\n            res.push_back(min(n, count));\n        }\n        else if (colors[q[1]] != q[2]) {\n            auto it = breaks.lower_bound(q[1]);\n            if (it != end(breaks) && *it == q[1])\n                erase(*it, breaks, cnt, n);\n            else\n                insert(q[1], breaks, cnt, n);\n            int pi = (q[1] == 0 ? n : q[1]) - 1;\n            if (colors[q[1]] != colors[pi])\n                insert(pi, breaks, cnt, n);\n            else\n                erase(pi, breaks, cnt, n);\n            colors[q[1]] = q[2];\n        }          \n    }\n    return res;\n}\n```
['C']