✅ C++ Beats 100% || Beginner Friendly ||  Easy Solution || With Comments || Winner's Solution ✅
The below solution is not mine, it is of @fjzzq2002  who ranked 1st in this contest\n\n\uD83E\uDDE9 Problem Overview\nGoal: Find the number of alternating group
**The below solution is not mine, it is of @fjzzq2002  who ranked 1st in this contest**\n\n\uD83E\uDDE9 Problem Overview\nGoal: Find the number of alternating groups in a list of colors for various queries, and efficiently handle updates to the list.\n\n\u2699\uFE0F Core Data Structures\nBinary Indexed Tree (BIT): Used for efficient range queries and updates.\nTwo BITs:\nB[0]: Tracks the length of groups.\nB[1]: Tracks the total number of groups.\n\n\n```\n#include <bits/stdc++.h>\nusing namespace std;\n#define SZ 63333\n#define fi first\n#define se second\ntypedef long long ll;\n#define mp make_pair\n#define pb push_back\n#define pii pair<int,int>\n\n// Function to calculate the length between two indices\nint len(int x, int y) {\n    return (y - x + 1);\n}\n\n// Overloaded function to calculate length for a pair\nint len(pii s) {\n    return len(s.fi, s.se);\n}\n\n// Binary Indexed Tree (BIT) class for efficient updates and queries\nstruct BB {\n    int bs[SZ]; // Array to store BIT values\n\n    // Update BIT: add value y to index x\n    void edt(int x, int y) {\n        x = SZ - 10 - x;\n        for (; x < SZ; x += x & -x) bs[x] += y;\n    }\n\n    // Query BIT: get the prefix sum up to index x\n    int qry(int x) {\n        x = SZ - 10 - x;\n        int ans = 0;\n        for (; x; x -= x & -x) ans += bs[x];\n        return ans;\n    }\n\n    // Clear BIT values up to index x\n    void clr(int x) {\n        x = SZ - 10 - x;\n        for (; x < SZ; x += x & -x) bs[x] = 0;\n    }\n} B[2];\n\n// Wrapper functions for updating and querying the BITs\nvoid edt(int x, int y) {\n    cerr << "edt::" << x << " " << y << "\\n";\n    B[1].edt(x, x * y); // Update second BIT with product of index and value\n    B[0].edt(x, y);     // Update first BIT with value\n}\n\nint qry(int x) {\n    return B[1].qry(x) + (1 - x) * B[0].qry(x); // Query BITs and combine results\n}\n\n// Main solution class\nclass Solution {\npublic:\n    // Main function to handle the queries\n    vector<int> numberOfAlternatingGroups(vector<int>& colors, vector<vector<int>>& queries) {\n        map<int, int> C; // Map to store start and end indices of alternating groups\n        int n = colors.size();\n\n        // Initialize alternating groups\n        for (int i = 0; i < colors.size(); ++i) {\n            int r = i;\n            // Find end of the current alternating group\n            while (r < colors.size() && (colors[r] + colors[i] + r + i) % 2 == 0) ++r;\n            C[i] = r - 1; // Store group boundaries in map\n            edt(r - i, 1); // Update BITs with new group\n            i = r - 1;     // Move to the end of the current group\n        }\n\n        vector<int> aa; // Vector to store results for type 1 queries\n\n        // Process each query\n        for (auto q : queries) {\n            if (q[0] == 1) { // Query type 1: Count alternating groups of a given size\n                int ans = qry(q[1]);\n                auto A = *C.begin(), B = *C.rbegin();\n                if (A != B) {\n                    // Check if merging groups is possible\n                    if (colors[0] != colors.back()) {\n                        int l1 = A.se - A.fi + 1;\n                        int l2 = B.se - B.fi + 1;\n                        ans -= max(l1 - q[1] + 1, 0); // Subtract groups that are too small\n                        ans -= max(l2 - q[1] + 1, 0);\n                        ans += max(l1 + l2 - q[1] + 1, 0); // Add merged group size\n                    }\n                } else if (colors[0] != colors.back()) {\n                    ans = n; // If there\'s only one group, check if it can span the entire array\n                }\n                aa.pb(ans); // Store result for type 1 query\n            } else { // Query type 2: Update color at a given index\n                int x = q[1], y = q[2];\n                if (colors[x] == y) continue; // If color is already correct, skip update\n                colors[x] = y; // Update color\n                // Find the block containing index x\n                auto it = C.upper_bound(x);\n                --it;\n                assert(it != C.end() && it->fi <= x && it->se >= x);\n                int L = it->fi, R = it->se;\n                edt(len(*it), -1); // Remove the old block\n                C.erase(it);\n                int ML = x, MR = x;\n                // Update or split the affected blocks\n                if (L != ML) {\n                    C[L] = x - 1;\n                    edt(len(L, x - 1), 1);\n                } else {\n                    if (x && colors[x] != colors[x - 1]) {\n                        auto it = C.upper_bound(x);\n                        --it;\n                        ML = it->fi;\n                        edt(len(*it), -1);\n                        C.erase(it);\n                    }\n                }\n                if (R != MR) {\n                    C[x + 1] = R;\n                    edt(len(x + 1, R), 1);\n                } else {\n                    if (x + 1 < colors.size() && colors[x + 1] != colors[x]) {\n                        auto it = C.upper_bound(x);\n                        MR = it->se;\n                        edt(len(*it), -1);\n                        C.erase(it);\n                    }\n                }\n                C[ML] = MR;\n                edt(len(ML, MR), 1); // Add new or modified block\n            }\n        }\n\n        // Clear BITs after processing all queries\n        for (int i = 0; i <= n + 2; ++i) B[0].clr(i), B[1].clr(i);\n\n        return aa; // Return results for type 1 queries\n    }\n};\n\n\n```\n\n**Approach to Solve the Problem**\n\n**1. Understanding the Problem**\nObjective: Determine the number of alternating color groups in a list for a series of queries.\n\n**Types of Queries:**\n\nCount the number of alternating color groups up to a given index.\nUpdate the color at a specific index and adjust the groupings accordingly.\n\n**2. Data Structures**\n\nBinary Indexed Tree (BIT):\nB[0]: Tracks the length of each alternating color group.\nB[1]: Tracks the number of alternating color groups.\nMap C: Maps the start index to the end index of each alternating color block.\n\n**3. Initialization**\n\n* Identify Alternating Groups:\nIterate through the colors list to find segments where the color alternates.\nUse the map C to store the start and end of each group.\n\n* Update BITs:\nFor each identified group, update the BITs to reflect the number of groups and their lengths.\n\n4. Processing Queries\n\nType 1 - Count Groups Up to Index:\n\n* Use the qry function to get the current count of groups up to the given index.\n* Check for Merge Possibility:\n* If the first and last colors are different, see if the groups at the start and end can be merged and adjust the count.\n\nType 2 - Update Color:\n\n* Find Block Containing Index:\n\tUse the map C to locate the block that includes the index to be updated.\n\n* Modify Groups:\n\tAdjust the blocks based on the new color. This might involve splitting or merging blocks.\n\n* Update BITs:\n\tReflect the changes in the BITs by updating group lengths and counts.\n\t\n5. Final Cleanup\nAfter processing all queries, clear the BITs to reset their state.
['C']