hackercupai/hackercup huggingface dataset:
We can still use the overall \(O(M + N \log N)\) disjoint sets strategy as in the previous chapter, but we can no longer keep track of colors in fixed bins. Let's switch to a different approach.

At any time, consider grouping consecutive balls of the same color (i.e. DSU representative) into \(G\) maximal groups. We can express this as a partition of \(N\), namely, a sequence of line segments \(S_1, ..., S_G\) with lengths summing to \(N\), where the color of stakes in each segment is uniform.

*Case 1*: Assume that \(N\) evenly divides \(K\). We can see that this partition is uniformly colored over every \(K\) stakes if \(K\) is a divisor of the lengths of all \(G\) segments. This is equivalent to requiring \(K\) be a divisor of \(\text{gcd}(S_1, ..., S_G)\). As long as we have the GCD, we can enumerate through all its divisors \(k\) and conclude that all bins of size \(k\) are uniformly colored.

*Case 2*: What if \(N\) doesn't divide \(K\)? We'll be left with a rightmost "remainder" bin of some length less than \(K\). Denote its length by \(R\):
* If the last segment's length \(|S_G| < K\), then the answer is NO, because the last two segments, having different colors, will necessarily overlap the last bin.
* Else \(|S_G| \ge K\), and we can consider breaking up \(S_G\) into two segments of lengths \(L = |S_G| - R\) and \(R\) (the right most bin) where \(|S_1| + ... + |S_{G-1}| + L\) evenly divides \(K\). Since stakes \(R..N\) are already the same color, this reduces to checking if \(K\) is a divisor of \(\text{gcd}(S_1, ..., S_{G-1}, L)\), which also requires \(K\) to be a divisor of \(\text{gcd}(S_1, ..., S_{G-1})\).

Case 2 simply reduces to running case 1 on all but the last segment.

We can use a data structure like an [implicit treap](https://cp-algorithms.com/data_structures/treap.html) to maintain the merging and splitting of segments in \(\mathcal{O}(\log N\)) time per insert/delete/access/select_kth operation. Whenever we update \(\text{parent}[i] = j\) in the DSU, we consider whether this breaks up an existing segment (of length longer than \(1\)) that \(i\) is part of, or whether it makes the parent of stake \(i\) equal to the preceding or following segment, in which case it can be merged.

The implicit treap also supports dynamic range queries like a segment tree, which we can use for the GCD. After each update, we query the GCD of the segment lengths and loop through up to \(\mathcal{O}(\sqrt{N})\) divisors. The overall running time is \(\mathcal{O}(M \sqrt N + N \log N)\).