Segment Tree Test

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 5.0s
Memory limit: 256M

Problem type

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

You have an array of N (1 \le N \le 100\,000) elements, indexed from 1 to N. There are M (1 \le M \le 500\,000) 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 the elements from the l-th to the r-th index, inclusive.
  • G l r Output the greatest common divisor of all the elements from the l-th to the r-th index, inclusive.
  • Q l r Output the number of numbers equal to the result of the operation G l r from all the elements from the l-th to the r-th index, inclusive.

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

Xyene 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 N and M.

The second line has N integers, the original array.

The next M 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


Sample Input 2

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

Sample Output 2



  • 2
    abcConjecture  commented on Feb. 6, 2018, 5:46 p.m. edited

    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?

  • -2
    0xc3  commented on Oct. 22, 2017, 10:56 a.m.

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

  • 4
    eric574  commented on May 18, 2017, 10:56 p.m.

    Why does UTSJoey's submission have 0 bytes?

    • 0
      Plasmatic  commented on Oct. 6, 2018, 11:00 p.m.

      it's probably a bug