I enjoyed this challenge. It took me a few days to come up with the right algorithm. In the process I learned to use mutable arrays in haskell, I learned a lot about lcm, gcd and module.

For all of you struggling: YES there is a solution that does not timeout in haskell.

My first try was the intuitive one: put all the values in an array, in every step either update the array or walk the array accumulating the lcm. This algorithm is O(1) for updates and O(n) for queries (assuming O(1) for lcm which is not true). This algorithm times out in several test cases.

My second try was to factorize the numbers and calculate the lcm by combining factorized numbers. The basic algorithm of storing the numbers an an array and either update them or calculate lcm of the range is the same. This algorithm is not faster than the previous one.

However, and this is a big tip: there is a way to do updates in O(log(n)) and queries in O(log(n)).