Submit solution

Points:
15 (partial)

Time limit:
2.5s

Memory limit:
256M

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

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.

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

Apparently unordered map is too slow.

I've been experiencing some erratic runtimes. One of my submissions received 90/100 (and passed Case 12 in about 2.5 seconds), but submitting the same code later yielded 60/100. Do I need to optimize my code in any way?

Does a solution with a time complexity of not work, or why is my solution TLEing?

Why does UTSJoey's submission have 0 bytes?

it's probably a bug