Alternating Groups III — Editorial

Opening the reading…

Intuitiona group is a window of consecutive color-changing edges

A group of size k is alternating exactly when every one of its k - 1 neighboring pairs has different colors. Mark edge i as good when colors[i] differs from colors[(i + 1) modulo n]. The group starting at tile s is valid precisely when the k - 1 edges starting at s are all good.

A maximal run of g consecutive good edges contains g - k + 2 valid starting positions when g is at least k - 1, and none otherwise. For example, with three required edges, a run of five good edges gives three windows. Therefore a query only needs the lengths of all good runs, not a scan of every starting tile.

DIAGRAM — NOT DRAWN YET

A ring of colored tiles has edges between neighboring tiles, including the edge from the last tile back to the first. Edges joining different colors are marked good, and edges joining equal colors are marked bad. The bad edges divide the ring into runs of consecutive good edges. A highlighted window covers k - 1 adjacent good edges inside one run, showing that its k tiles form one valid alternating group.

A color update changes only two edges: the edge entering the changed tile and the edge leaving it. Store the bad edges in an ordered set. When one bad edge is inserted, it splits one circular good run into two; when it is removed, two neighboring runs merge. The remaining challenge is summing max(0, g - k + 2) over all run lengths g, which two Fenwick trees handle by length.

Approach

Represent edge i by the pair of tiles i and (i + 1) modulo n, and call it bad when those colors are equal. A group of size k then needs L = k - 1 consecutive good edges, so checking colors directly is no longer necessary for type 1 queries.

Insert every initially bad edge into an ordered set. If the set is nonempty, consecutive bad edges p and q enclose a good run of length (q - p - 1 + n) modulo n, which gives one run length to maintain.

Maintain one Fenwick tree for how many runs have each length and another for the sum of those lengths. Keeping both lets a query collect all runs with length at least L and evaluate their contributions without visiting them one by one.

For a type 1 query, find the number of runs with g at least L and the sum of their lengths. Their total contribution is sumG - (L - 1) times countG, because each such run contributes g - L + 1 valid windows; shorter runs contribute zero.

For a type 2 query, remove the two affected edge states before changing the tile color. This removes the old bad edges and merges any runs that the update joins, rather than trying to repair a structure that still describes the old colors.

Change colors[index], recompute the entering and leaving edges, and insert their new bad states. Each insertion splits one run into two, so only a constant number of Fenwick entries changes.

Handle the no-bad-edge case separately: the whole circle is alternating, and every one of the n starting positions forms a valid group because the requested size is at most n - 1.

Complexityordered neighbors plus two Fenwick trees

MEASURE	BOUND	WHY
Time	O((n + q) log n)	Building the bad-edge set and its run frequencies performs O(n) ordered-set and Fenwick operations. Each update touches two edges, causing only constant-many splits or merges, and each type 1 query uses constant-many Fenwick sums, so every query costs O(log n).
Space	O(n)	The ordered set can contain every edge, and the two Fenwick trees each have n length positions. The returned answer array is required output and is excluded from the extra-space bound; the worst shape, with many alternating runs, still uses only these linear structures.

n is the number of tiles and q is the number of queries. The requested size is k, and each query uses L = k - 1 required good edges.

Annotated solutionC++ · dynamic circular runs with Fenwick trees

CPPThe complete solution maintains bad edges, circular gap lengths, and threshold sums with two Fenwick trees.

#include <vector>
#include <set>
using namespace std;

class Solution {
    struct Fenwick {
        int n;
        vector<long long> tree;

        Fenwick(int n) : n(n), tree(n + 1, 0) {}

        void add(int index, long long value) {
            for (; index <= n; index += index & -index) {
                tree[index] += value;
            }
        }

        long long sum(int index) const {
            long long result = 0;
            for (; index > 0; index -= index & -index) {
                result += tree[index];
            }
            return result;
        }

        long long rangeSum(int left, int right) const {
            if (left > right) return 0;
            return sum(right) - sum(left - 1);
        }
    };

public:
    vector<int> numberOfAlternatingGroups(vector<int>& colors, vector<vector<int>>& queries) {
        int n = static_cast<int>(colors.size());
        set<int> bad;
        Fenwick frequency(n + 1);
        Fenwick lengthSum(n + 1);

        auto isBad = [&](int edge) {
            int next = (edge + 1) % n;
            return colors[edge] == colors[next];
        };

        auto gapLength = [&](int from, int to) {
            return (to - from - 1 + n) % n;
        };

        auto addGap = [&](int from, int to, int delta) {
            int length = gapLength(from, to);
            int position = length + 1;
            frequency.add(position, delta);
            lengthSum.add(position, 1LL * delta * length);
        };

        for (int edge = 0; edge < n; ++edge) {
            if (isBad(edge)) bad.insert(edge);
        }

        if (!bad.empty()) {
            auto it = bad.begin();
            int first = *it;
            int previous = first;
            ++it;
            for (; it != bad.end(); ++it) {
                addGap(previous, *it, 1);
                previous = *it;
            }
            addGap(previous, first, 1);
        }

        auto removeBad = [&](int edge) {
            auto it = bad.find(edge);
            if (it == bad.end()) return;

            if (bad.size() == 1) {
                addGap(edge, edge, -1);
                bad.erase(it);
                return;
            }

            auto previousIt = (it == bad.begin()) ? prev(bad.end()) : prev(it);
            auto nextIt = next(it);
            if (nextIt == bad.end()) nextIt = bad.begin();

            int previous = *previousIt;
            int next = *nextIt;
            addGap(previous, edge, -1);
            addGap(edge, next, -1);
            addGap(previous, next, 1);
            bad.erase(it);
        };

        auto insertBad = [&](int edge) {
            if (bad.empty()) {
                bad.insert(edge);
                addGap(edge, edge, 1);
                return;
            }

            auto nextIt = bad.lower_bound(edge);
            if (nextIt == bad.end()) nextIt = bad.begin();
            auto previousIt = (nextIt == bad.begin()) ? prev(bad.end()) : prev(nextIt);

            int previous = *previousIt;
            int next = *nextIt;
            addGap(previous, next, -1);
            addGap(previous, edge, 1);
            addGap(edge, next, 1);
            bad.insert(edge);
        };

        vector<int> answer;
        for (const vector<int>& query : queries) {
            if (query[0] == 1) {
                int requiredEdges = query[1] - 1;

                if (bad.empty()) {
                    answer.push_back(n);
                    continue;
                }

                int firstPosition = requiredEdges + 1;
                long long count = frequency.rangeSum(firstPosition, n + 1);
                long long totalLength = lengthSum.rangeSum(firstPosition, n + 1);
                long long valid = totalLength - 1LL * (requiredEdges - 1) * count;
                answer.push_back(static_cast<int>(valid));
            } else {
                int index = query[1];
                int color = query[2];
                int entering = (index - 1 + n) % n;
                int leaving = index;

                removeBad(entering);
                removeBad(leaving);
                colors[index] = color;
                if (isBad(entering)) insertBad(entering);
                if (isBad(leaving)) insertBad(leaving);
            }
        }

        return answer;
    }
};

The key update order is remove, mutate, insert. Removing both affected edges first makes the set describe the color arrangement before the update; changing the tile then gives the two new edge states. The single-bad-edge case represents one run from that edge back to itself, with n - 1 good edges, so it must be recorded rather than treated as an empty structure.