At first divide the array into sqrt(n) blocks, where each block contains sqrt(n) elements. This trick is called sqrt decomposition. Then the update queries can be done using a DSU (Disjoint Set Union) in each block.

Total time complexity is O(q × sqrt(n)). Here m is the number of queries and n is the size of the array.

This problem can also be solved using brute force, by using some compiler optimization trick. Setters were not aware of this technique, but some (Almost everyone having an AC solution of E) contestants have solved this problem using that. You can learn about that technique here.


59% Solution Ratio
MamnoonSiamEarliest, Apr '20
asdfghjFastest, 0.1s
riyad000Lightest, 823 kB
hamtydamtyShortest, 350B
Toph uses cookies. By continuing you agree to our Cookie Policy.