Segment Tree Test

View as PDF

Submit solution

Points: 15
Time limit: 2.5s
Memory limit: 512M

Problem type

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

Each operation is one of the following:

  • C x v change the x-th element of the array to v.
  • M l r output the minimum of all elements between indicies l and r, inclusive.
  • G l r output the greatest common divisor of all elements between indicies l and r, inclusive.
  • Q l r let G be the result of G l r right now. Output the number of elements between indicies l and r, inclusive, equal to G.


1 \le N \le 10^5

1 \le M \le 5 \times 10^5

At any time, every element in the array is between 1 and 10^9, inclusive.

Input Specification

The first line contains N and M.

The second line contains N integer,s the original array.

The next M lines each contain an operation as described above.

Output Specification

For each M, G, and Q query, output the answer on a new 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


Sample Input 2

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

Sample Output 2



There are no comments at the moment.