Straightforward Java | O(N*log(N) + Q*(log(N) + sqrt(N))) time | O(N + Q) space | No BIT or SegTree
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThe first useful observation is that the array can be split into a set of maximum alt
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe first useful observation is that the array can be split into a set of maximum alternating groups. Each group of size K contains 1 group of K elements, 2 groups of (K-1) elements, ... and K different groups of 1 element.\n\nNow we can easily solve the task for a single count query in linear time or for multiple count queries in `O(N + Q)` time if we index the input data in advance (e.g. by pre-computing all counters).\n\nThe problem arises when we need to support update queries. Simple indices like a map with counters get screwed in no time and need to be re-built after every update.\n\nAt this moment we can remember about smart ways to handler updates and range queries by using a Binary Index Tree (BIT) or a Segment Tree as the tags and most solutions here suggest.\n\nI though so too and have finally learned how BIT works. I\'d been going to do it for a long time and was glad that the moment had finally approached. But the good stuff ends here for me. I still don\'t get it quite well how to apply these structures to this problem even after checking other solutions.\n\nThanks to one of previous hard string questions I\'ve noticed that, even though the input array is big, the amount of unique group lengths in it is limited by square root of N. We get this maximum amount of groups if we have groups of size 1, 2, .., K. They represent an arithmetic progression and sum up to `K*(K+1) / 2`. For 50k input elements the max number of unique group sizes we get is 223 (`= sqrt(50_000)`).\n\nAs the number looks bearable, let\'s try to simply implement the brute force approach with grouping of current segment sizes. This way we can support update queries which are explained below.\n\nSo here goes my dumb and slow straightforward 120-liner. Beats about 10% of other java solutions.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nLet\'s proceed with the initial idea and build 2 indices:\n- a hash map of maximum segemnts: `map<start, length>`\n- a map with counters for each unique group length: `map<group_length, counter>`\n\nFor update queries we iterate over all unique lengths, calculating the number of gruops as `max(1 + len - size, 0)` except for a case when all elements are in a cycle and there are N groups of any size from 1 to N.\n\nFor update queries we optionally break one of the current group that the updated element belongs to into 1, 2 or 3 groups, e.g. like spliiting \'1010101\' into \'101\' + \'1\' + \'101\'. In case the updated element is the first or / and the last element of the group it will need extra merging with neighbour groups (both of them if the upgraded group had length equal 1).\nUpdate steps:\n1. For the current group containing the updated element:\n    - remove the current group from the maps\n    - re-add the head / prefix group if it\'s not empty\n    - re-add the tail / suffix group if it\'s not empty\n    - extra attention is needed when breaking the only group of size N not to re-add it twice or select a new start in an inappropriate position in case of a perfect cycle\n2. Keep the updated element as a new group of size 1.\n    - if the next group\'s first element is different from the updated value, remove the next group and append it to the new one (actually the next group always has to be merged in case the updated element was the last in its group as the next group\'s first element was equal to the previous value of the updated element, for that reason they weren\'t in the same group)\n    - if the previous group\'s last element is different from the updated value, remove the previous group and merge it with the new one\n    - special handling is needed when both previous and next groups are the same\n    - finally, add the new group to both index maps\n\n# Complexity\n- Time complexity: $$O(N*log(N) + Q*(log(N) + sqrt(N)))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\nWe add the original colors array of `N` elements into the index maps in `N * log(N)` operations (each put call into TreeMap is `log(N)`).\nThen for `Q` queries we either count groups in `sqrt(N)` each or updating the index maps in `log(N)` each.\n\n- Space complexity: $$O(N + Q)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nWe keep two group index maps of maximum size `N`.\nWe also need up to `Q` result elements for count queries.\n\n# Code\n```\nclass Solution {\n    TreeMap<Integer, Integer> treeMap = new TreeMap<>(); // map[group_start] = len\n    Map<Integer, Integer> lengthCnt = new HashMap<>(); // map[group_len] = counter\n\n    public List<Integer> numberOfAlternatingGroups(int[] colors, int[][] queries) {\n        int n = colors.length;\n\n        // getting and indexing all alternating group starts\n        int start = 1;\n        while (start < n && colors[start] != colors[start - 1]) {\n            start++; // looking for a good first \'cut\'\n        }\n        start = start % n;\n        int lastEnd = start;\n        for (int i = start; i < n;) {\n            int end = i + 1;\n            while (end - i < n && colors[end % n] != colors[(end + n - 1) % n]) {\n                end++; // max possible end-start len is N\n            }\n            addGroup(i, end - i);\n            i += end - i;\n            lastEnd = end % n;\n        }\n        if (lastEnd != start) { // the last group spans over the end of the array\n            addGroup(lastEnd, (start + n - lastEnd) % n);\n        }\n\n        List<Integer> result = new ArrayList<>();\n        for (int[] q : queries) {\n            if (q[0] == 1) { // count query\n                int size = q[1];\n                int cnt = 0;\n                for (int len : lengthCnt.keySet()) {\n                    int subGroups = len == n && isSingleCycle(treeMap.keySet().iterator().next(), len, colors) ?\n                        n /* == len -> any positions is a good group start */ :\n                        Math.max(1 + len - size, 0);\n                    cnt += subGroups * lengthCnt.get(len);\n                }\n                result.add(cnt);\n            } else { // update query\n                int updateIdx = q[1];\n                int newValue = q[2];\n                if (newValue == colors[updateIdx]) {\n                    continue; // nothing changes\n                }\n\n                updateValue(colors, updateIdx, newValue);\n            }\n        }\n        return result;\n    }\n\n    private void updateValue(int[] colors, int updateIdx, int newValue) {\n        int n = colors.length;\n\n        // cases: group split, groups merge\n        int groupStart = Objects.requireNonNullElse(treeMap.floorKey(updateIdx), treeMap.floorKey(updateIdx + n));\n        int groupLen = removeGroup(groupStart);\n        int groupEnd = (groupStart + groupLen) % n;\n\n        // 1) let\'s detach head & tail groups if any, so updateIdx becomes a 1-len group\n        int headStart = groupStart;\n        int headLen = (updateIdx + n - headStart) % n; // %n is safe here max len is n-1 here\n        int tailStart = (updateIdx + 1) % n;\n        int tailLen = (groupEnd + n - tailStart) % n; // ^ ... b/c updateLen == 1\n        if (isSingleCycle(groupStart, groupLen, colors)) {\n            addGroup(tailStart, n - 1);\n        } else {\n            if (headLen > 0) {\n                addGroup(headStart, headLen);\n            }\n            if (tailLen > 0) {\n                addGroup(tailStart, tailLen);\n            }\n        }\n\n        // 2) now we have a single missing cell - updatedCell, let\'s merge it with\n        // neighbours if possible\n        int newStart = updateIdx;\n        int newLen = 1;\n        int prevStart = Objects.requireNonNullElse(treeMap.floorKey(newStart), treeMap.floorKey(newStart + n));\n        int nextStart = Objects.requireNonNullElse(treeMap.ceilingKey(newStart), treeMap.ceilingKey(newStart - n));\n        colors[newStart] = newValue;\n        boolean nextJoined = false;\n        if ((newStart + 1) % n == nextStart && colors[newStart] != colors[nextStart]) {\n            // merging with the next group\n            newLen += removeGroup(nextStart);\n            nextJoined = true;\n        }\n        if ((prevStart != nextStart || !nextJoined) && colors[(newStart + n - 1) % n] != colors[newStart]) {\n            // merging with the previous group\n            newLen += removeGroup(prevStart);\n            newStart = prevStart;\n        }\n        addGroup(newStart, newLen);\n    }\n\n    private void addGroup(int start, int len) {\n        treeMap.put(start, len);\n        lengthCnt.compute(len, (k, v) -> (v != null ? v : 0) + 1);\n    }\n\n    private int removeGroup(int start) {\n        int len = treeMap.remove(start);\n        lengthCnt.compute(len, (k, v) -> v == 1 ? null : v - 1);\n        return len;\n    }\n\n    // checking if we have a single cycle of length N without any break point\n    private boolean isSingleCycle(int start, int len, int[] colors) {\n        int n = colors.length;\n        if (len == n) {\n            if (colors[start] != colors[(start + n - 1) % n]) {\n                return true;\n            }\n        }\n        return false;\n    }\n}\n```
['Ordered Map', 'Counting', 'Java']