Fenwick | Sorted Map | Xor Array | N*log(n)+M*log(n)
we need to use helper xor array for each x[i] element x[i] = colors[i] ^ colors[i + 1]. Note: If xor array is [01110] the longest subarray of alternating colors
- we need to use helper xor array for each `x[i]` element `x[i] = colors[i] ^ colors[i + 1]`. **Note:** If xor array is `[01110]` the longest subarray of alternating colors is `3 + 1 = 4`.\n- we need to track subarrays of xor where all elements are 1s. we will use sorted map called `interval` for that, if the xor array is `[1101011]` the interval will be `[{0,1}, {3,3}, {5,6}]`. **Note:** don\'t represent the `interval` sorted map like this `[{3,3}, {5,1}]`, because it will complicate the problem more.\n- we use Fenwick tree to count length of intervals and frequencies of intervals\n- we will temporaliy the fenwick array only on `type 1` query, to merge the first and last elements of the `interval` sorted map if it\'s relevant (i.e. key of the first item of `interval` and value of the last item of `interval` are neightbors in the cycle like `0` in `{0, 1}` and `6` in `{5, 6}` in the example above). we well undo the temporary merge after adding the answer. \n\n# Code\n```\n// Using Fenwick for tracking interval sizes and frequencies\nclass Fenwick {\nprivate:\n    int n;\n    vector<int> f; // track lengths of intervals\n    vector<int> fq; // track frequencies\npublic:\n    Fenwick(int n){\n        this->n = n;\n        f = vector(n + 2, 0);\n        fq = vector(n + 2, 0);\n    }\n\n    void add(int idx) {\n        // Fenwick array starts with the index 1 so we increase idx by 1 since xor array is 0 based\n        for(int size = ++idx; idx <= n + 1; idx += idx & (-idx)) {\n            f[idx] += size;\n            fq[idx] += 1;\n        }\n    }\n\n    void remove(int idx) {\n        // Fenwick array starts with the index 1 so we increase idx by 1 since xor array is 0 based\n        for(int size = ++idx; idx <= n + 1; idx += idx & (-idx)) {\n            f[idx] -= size;\n            fq[idx] -= 1;\n        }\n    }\n\n    int getSum(int idx) {\n        int sum = 0;\n        for (;idx > 0; idx -= idx & (-idx)) {\n            sum += f[idx];\n        }\n        \n        return sum;\n    }\n\n    int getFreq(int idx) {\n        int freq = 0;\n        for(;idx > 0; idx -= idx & (-idx)) {\n            freq += fq[idx];\n        }\n\n        return freq;\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> numberOfAlternatingGroups(vector<int>& colors, vector<vector<int>>& queries) {\n        int n = colors.size();\n\n        vector<int> ans;\n\n        // inline helper functions\n        auto getIdx = [&](int idx) -> int { return (idx + n) % n; };\n        // param a must be more than or equal to param b\n        auto getSize = [&](int a, int b) -> int { return getIdx(a) - getIdx(b) + 1; };\n\n        Fenwick fen = Fenwick(n);\n\n        vector x(n, 0); // xor array is color[i] ^ color[i + 1]\n\n        // build xor array\n        for (int i = 0; i < n; i++) {\n            x[i] = colors[i] ^ colors[(i + 1) % n];\n        }\n\n        int l = INT_MAX;\n        map<int, int> interval; // sorted map key is left index of the interval, value is the right Index\n        // find the interval in log(n)\n        auto findInterval = [&](int idx)-> map<int, int>::iterator {\n          return interval.find(idx) == interval.end() && interval.size() > 0\n                        ? (--interval.lower_bound(idx))\n                        : (interval.lower_bound(idx));\n        };\n\n        // build intervals according to xor array\n        for (int i = 0; i < n; i++) {\n            if (x[i] == 1) {\n                l = min(l, i);\n                interval[l] = i;\n                if (x[getIdx(i + 1)] == 0 || i + 1 == n) {\n                    fen.add(getSize(i, l));\n                }\n            } else {\n                l = INT_MAX;\n            }\n        }\n\n        // add new interval with size 1\n        auto add = [&](int idx) {\n            interval[idx] = idx;\n            fen.add(1);\n        };\n\n        // split intervals\n        auto split = [&](int idx) {\n            auto it = findInterval(idx);\n            auto [left, right] = *it;\n            interval.erase(it);\n\n            fen.remove(getSize(right, left));\n\n            if(left == right){\n                return;\n            }\n\n            if (idx == left) {\n                interval[idx + 1] = right;\n                fen.add(getSize(right, idx + 1));\n            } else if (idx == right) {\n                interval[left] = idx - 1;\n                fen.add(getSize(idx - 1, left));\n            } else {\n                interval[left] = idx - 1;\n                fen.add(getSize(idx - 1, left));\n\n                interval[idx + 1] = right;\n                fen.add(getSize(right, idx + 1));\n            }\n        };\n\n        // merge intervals, leftIdx is always less then rightIdx\n        auto merge = [&](int leftIdx, int rightIdx) {\n            auto leftIt = findInterval(leftIdx);\n\n            auto rightIt = findInterval(rightIdx);\n\n            if(leftIt == rightIt){\n                return;\n            }\n\n            auto [left0, right0] = *leftIt;\n            auto [left1, right1] = *rightIt;\n\n            interval.erase(leftIt);\n            fen.remove(getSize(right0, left0));\n            interval.erase(rightIt);\n            fen.remove(getSize(right1, left1));\n\n            interval[left0] = right1;\n            fen.add(getSize(right1, left0));\n        };\n\n        // if the first and last intervals can be merged we do it\n        auto connectEnds = [&]()->bool {\n            if(interval.size() < 2) {\n                return false;\n            }\n\n            auto [left0, right0] = *interval.begin();\n            auto [left1, right1] = *interval.rbegin();\n\n            if(getIdx(right1 + 1) == left0){\n                fen.remove(getSize(right0, left0));\n                fen.remove(getSize(right1, left1));\n                fen.add(getSize(right0, left0) + getSize(right1, left1));\n\n                return true;\n            }\n\n            return false;\n        };\n\n        // undo merge of the first and last intervals\n        auto disconnectEnds = [&]() {\n            auto [left0, right0] = *interval.begin();\n            auto [left1, right1] = *interval.rbegin();\n            fen.remove(getSize(right0, left0) + getSize(right1, left1));\n            fen.add(getSize(right0, left0));\n            fen.add(getSize(right1, left1));\n        };\n\n        for (auto& query : queries) {\n            int type = query[0];\n            if (type == 1) {\n                int k = query[1];\n                bool connected = connectEnds();\n\n                int sum = fen.getSum(n + 1) - fen.getSum(k - 1);\n                int freq = fen.getFreq(n + 1) - fen.getFreq(k - 1);\n\n                ans.push_back(sum == n + 1 ? n : sum - freq * (k - 1));\n\n                if(connected) {\n                    disconnectEnds();\n                }\n            }\n            else {\n                int idx = query[1];\n                int color = query[2];\n                if (colors[idx] == color)\n                    continue;\n\n                colors[idx] = color; // update colors array\n\n                // update xor array (only 2 elements are updated others are remaining the same)\n                x[getIdx(idx - 1)] = colors[getIdx(idx - 1)] ^ colors[idx];\n                x[idx] = colors[idx] ^ colors[getIdx(idx + 1)];\n\n                // updated xor elements\n                int xLeft = x[getIdx(idx - 1)];\n                int xRight = x[idx];\n\n                // neighbors of updated xor elements\n                int leftMost = x[getIdx(idx - 2)];\n                int rightMost = x[getIdx(idx + 1)];\n\n                // update intervals\n                if(xLeft){\n                    add(getIdx(idx - 1));\n                    // we merge the leftMost and xLeft if and only if leftMost and xLeft are properly ordered\n                    if (leftMost && getIdx(idx - 2) < getIdx(idx - 1)){\n                        merge(getIdx(idx - 2), getIdx(idx - 1));\n                    }\n                }\n                else {\n                    split(getIdx(idx - 1));\n                }\n\n                if(xRight){\n                    add(idx);\n                    // we merge the xRight and rightMost if and only if xRight and rightMost are properly ordered\n                    if(rightMost && idx < getIdx(idx + 1)){\n                        merge(idx, idx + 1);\n                    }\n                }\n                else {\n                    split(idx);\n                }\n\n                // we merge the xLeft and xRight if and only if xLeft and xRight are properly ordered\n                if(xLeft && xRight && getIdx(idx - 1) < idx){\n                    merge(idx - 1, idx);\n                }\n            }\n        }\n\n        return ans;\n    }\n};\n```
['Bit Manipulation', 'Binary Indexed Tree', 'Ordered Map', 'C++']