Submit solution

Points:
15 (partial)

Time limit:
1.0s

Java
1.5s

Python
2.5s

Memory limit:
256M

Problem type

is doing a contest. He comes across the following problem:

You have an array of elements, indexed from to . There are operations you need to perform on it.

Each operation is one of the following:

`C x v`

Change the -th element of the array to .`M l r`

Output the minimum of all the elements from the -th to the -th index, inclusive.`G l r`

Output the greatest common divisor of all the elements from the -th to the -th index, inclusive.`Q l r`

Let be the result of the operation`G l r`

right now. Output the number of elements from the -th to the -th index, inclusive, that are equal to .

At any time, every element in the array is between and (inclusive).

knows that one fast solution uses a Segment Tree. He practices that data structure every day, but still somehow manages to get it wrong. Will you show him a working example?

#### Input Specification

The first line has and .

The second line has integers, the original array.

The next lines each contain an operation in the format described above.

#### Output Specification

For each `M`

, `G`

, or `Q`

operation, output the answer on its own line.

#### Sample Input 1

```
5 5
1 1 4 2 8
C 2 16
M 2 4
G 2 3
C 2 1
Q 1 5
```

#### Sample Output 1

```
2
4
2
```

#### Sample Input 2

```
5 2
1 1 2 2 2
Q 1 4
Q 3 5
```

#### Sample Output 2

```
2
3
```

## Comments

https://dmoj.ca/submission/1143175 has some interesting variable names....

How big is case 15? Why must we optimize our code so much?

My solution using a recursive segment tree with no constant optimizations passes in 1.370s in the worst case.

My hint for you is to answer all queries using a segment tree:

`std::unordered_map`

is extremely slow.Oh I thought it was always constant time.

I think accessing an unordered_map key is O(1) but it has a really bad constant factor. I could be wrong but believe it is almost as slow as O(logN).

My solution is but is getting TLE verdict from Case 12 onward. Any tips to optimize?

iam not sure , but may try iterative segment tree (not sure if it's feasible to implement it easily) , also try unordered map or any optimised map for 4th query

I tried using iterative segtree but it's still too slow: https://dmoj.ca/submission/3191595

Ruby won't work here unfortunately, its about as fast as CPython.

Apparently unordered map is too slow.