The origin statment of the problem can be found here.

In short, this problem ask you to do two operations on an array, one is to query the least common multipler(lcm) of an range [l, r], and another is to update one value of the array.

Since the maximum length of the array is , an naive algorithm will definitively not acceptable. So we need to find more efficient way to do the query and update operations.

The solution is to use a structure called segment tree to make the query and update operations run in time complexity.

Segment tree is often used in scenario of efficient range query and update. The following is an example of segment tree.

In segment tree, all the leaf nodes store the information of the segment
value, and the internal node store the result of a range `[l, r]`

.

The pseudo codes of query and update are:

```
function query(f, l, r, root):
if l <= root.left and root.right <= r:
return root.val
else if r <= root.leftChild.right:
return query(f, l, r, root.leftChild)
else if l >= root.rightChild.left:
return query(f, l, r, root.rightChild)
else:
return f(query(f, l, r, root.leftChild),
query(f, l, r, root.rightChild))
function update(f, idx, newVal, root):
if idx <= root.left and root.right <= idx:
root.val = newVal
else if idx <= root.leftChild.right:
root.val = f(newVal, root.val)
update(f, idx, newVal, root.leftChild)
else:
root.val = f(newVal, root.val)
update(f, idx, newVal, root.rightChild)
```

At first glance, the running time of `query`

is not explicit .
But you can find the proof from the stackoverflow answer, which shows
that the running time of the `query`

function is actually .

Then the solution is trival. We use an segment tree to store the lcm
information. The node cover range `[l, r]`

is the lcm of the elements in
`array[l..r]`

. So both the update and query operator can be done in .

The following is a least common multiple segment tree example.

The circle nodes are leaf nodes and store the numbers in the array, and the rectangle nodes store range lcm information as described in the brackets in the node.

Here is the haskell code of the segment tree structure

```
data SegTree =
Node {
val :: Integer
, left, right :: Int
, leftChild, rightChild :: SegTree
} |
Leaf {
val :: Integer
, left, right :: Int
}
initSegTree :: Int -> SegTree
initSegTree n = aux 0 (n - 1)
where aux l r
| l == r = Leaf {val = -1, left = l, right = r}
| otherwise =
let mid = (l + r) `div` 2
in Node { val = -1, left = l, right = r
, leftChild = aux l mid
, rightChild = aux (succ mid) r
}
query :: (Int, Int) -> SegTree -> Integer
query range@(l, r) root
| r < left root = 1
| l > right root = 1
| l <= left root && right root <= r = val root
| otherwise =
lcm (query range (leftChild root)) (query range (rightChild root))
update :: Int -> Integer -> SegTree -> SegTree
update idx newVal root
| left root <= idx && idx <= right root =
case root of
Leaf {} -> root {val = newVal }
_ -> root {val = lcm newVal (val root),
leftChild = lChild, rightChild = rChild }
| otherwise = root
where
lChild = update idx newVal $ leftChild root
rChild = update idx newVal $ rightChild root
```

In fact, since haskell is an pure functional languages, it should
be a little trival to do programming related with states in it. But since
the character of programming contests problems. We do not need to use
state manipulation in haskell to get the problem accept, we can just
use purely functional style to do the `query`

and `update`

operators using
`fold`

in haskell.

The following code is related with solving the problem.

```
processQueries
:: [(Char, Int, Int)] -> SegTree -> [Integer] -> [Integer]
processQueries [] _ acc = reverse acc
processQueries (('Q', l, r):q) root acc =
let ans = (query (l, r) root) `mod` modulo
in processQueries q root (ans : acc)
processQueries ((_, idx, value):q) root acc =
let oldVal = query (idx, idx) root
newVal = oldVal * (fromIntegral value)
nroot = update idx newVal root
in processQueries q nroot acc
solve :: Int -> [Integer] -> [(Char, Int, Int)] -> [Integer]
solve n arr queries = processQueries queries tree []
where
tree = foldl' (\ root (idx, v) -> update idx v root)
(initSegTree n)
(zip [0..] arr)
```

The only thing one should notice is that the depth limit of stack on
HackerRank is quite small. So we need to avoid too deep recursive
call, and use the strick version of `foldl'`

call in the `solve`

function,
and also avoid explicit recursive call in `processQueries`

, but to optimize
the function as an tail recursive call.

The full code can be found here.

m00nlight 11 April 2015