[C++] | Interval Maintenance + 1D Fenwick Tree Difference | O(Nlog(N))
\n#define lowbit(v)       (v&-v)\ntypedef pair<int,int>   pii;\nconst int               N = 10 + 1e5;\n\n/* ----------------------------------------------------
```\n#define lowbit(v)       (v&-v)\ntypedef pair<int,int>   pii;\nconst int               N = 10 + 1e5;\n\n/* ---------------------------------------------------------------------------------------------------- */\n// 1D Fenwick Tree Difference\nint     T;\nint     t1[N];\nint     t2[N];\n\nvoid update(int k, int val) {\n    for (int i = k; i <= T; i+=lowbit(i)) t1[i] += val, t2[i] += k*val;\n}\n\nint ask(int k) {\n    int ans = 0;\n    for (int i = k; i >= 1; i-=lowbit(i)) ans += (k+1)*t1[i] - t2[i];\n    return ans; \n}\n\n\n\nclass Solution {\npublic:\n    vector<int> numberOfAlternatingGroups(vector<int>& a, vector<vector<int>>& queries) {       int n = a.size();\n        // Preprocessing 1:     Obtain the alternating array from the original array\n        map<int,int> st;\n        for (int l = 0, r = 0; l < n; l = r) {\n            for (r = l+1; r-l+1 <= n && a[r%n]!=a[(r-1)%n]; r++);\n            st[(r-1)%n] = l;\n        }\n\n\n        /* -------------------------------------------------------------------------------- */\n        // Helper Function\n        auto find = [&](int i) -> map<int,int>::iterator { auto p = st.lower_bound(i); return p != st.end() ? p : st.begin(); };\n        auto len  = [&](int l, int r) -> int { return r<l ? (r+n-l+1) : r-l+1; };\n        auto check = [&]() -> bool {  return st.size() == 1 && a[st.begin()->first]!=a[st.begin()->second]; };\n        // Interval Maintenance 0:  Remove the interval containing index i and return the interval [l, r]\n        auto del = [&](int i) -> pii {\n            auto p = find(i); auto [r,l] = *p; st.erase(p);\n            update(n+1-len(l,r), -1);\n            return {r,l};\n        };\n        // Interval Maintenance 1:  Add the interval [l, r]\n        auto add = [&](int l, int r) {      \n            st[r] = l;\n            update(n+1-len(l,r), 1);\n        };\n        /* -------------------------------------------------------------------------------- */\n\n\n        // Preprocessing 2:     Initialize the Fenwick Tree\n        memset(t1, 0, sizeof(int)*(n+10));\n        memset(t2, 0, sizeof(int)*(n+10));\n        T = n;\n        for (auto& [r,l] : st) update(n+1-len(l,r), 1);\n\n                                                                                         \n        vector<int> ans;\n        for (auto& e : queries) {\n            if (e[0] == 2) {\n                int i = e[1], val = e[2];   \n                if (a[i] == val) continue;\n                a[i] = val;\n\n                auto [r,l] = del(i); \n         \n                if (l == r) {                               // Only merging\n                    int u = (i-1+n)%n, v = (i+1)%n;\n                    if (u != i && a[u]!=a[i] && !st.empty()) l = del(u).second;\n                    if (v != i && a[v]!=a[i] && !st.empty()) r = del(v).first;\n                    add(l, r);\n                }\n                else if (i == l) {                          // Split with the right side, merge with the left side\n                    add((i+1)%n, r);\n                    int u = (i-1+n)%n;\n                    if (u != i && a[u]!=a[i] && !st.empty()) l = del(u).second;\n                    add(l, i);\n                }\n                else if (i == r) {                          // Split with the left side, merge with the right side\n                    add(l, (i-1+n)%n);\n                    int v = (i+1)%n;\n                    if (v != i && a[v]!=a[i] && !st.empty()) r = del(v).first;\n                    add(i, r);\n                }\n                else {                                      // Split with both the left and right sides\n                    int u = (i-1+n)%n, v = (i+1)%n;\n                    if (len(l,r)==n && a[l]!=a[r])  add(v, u);\n                    else                            add(l, u), add(v, r);\n                    add(i, i);\n                }            \n            } else {\n                ans.push_back(check() ? n : ask(n+1-e[1]));\n            }\n        }\n                                                                                         \n        return ans;\n    }\n};\n\n```
[]