Segment Tree Test

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.5s
Java 1.0s
Python 2.5s
Memory limit: 16M
Python 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 Let G be the result of the operation G l r right now. Output the number of elements from the l-th to the r-th index, inclusive, that are equal to G.

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

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


  • 19
    dxke02  commented on Feb. 4, 2021, 7:52 p.m.

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


  • 0
    31501357  commented on Nov. 21, 2020, 3:06 a.m.

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


    • 3
      Kirito  commented on Nov. 21, 2020, 3:38 a.m. edited

      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.


      • 2
        31501357  commented on Nov. 21, 2020, 10:29 p.m.

        Oh I thought it was always constant time.


        • 3
          Marshmellon  commented on Sept. 11, 2021, 6:46 p.m. edited

          I think accessing an unordered_map key is \mathcal{O}(1) but it has a really bad constant factor. I could be wrong but believe it is almost as slow as \mathcal{O}(\log N).


  • 0
    Plasmatic  commented on Oct. 31, 2019, 12:04 p.m. edited

    My solution is \mathcal{O}(Q \log N) but is getting TLE verdict from Case 12 onward. Any tips to optimize?


    • 0
      stringray  commented on Oct. 31, 2019, 2:42 p.m.

      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


      • 0
        Plasmatic  commented on Dec. 8, 2020, 9:49 p.m.

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


        • -3
          c  commented on Dec. 9, 2020, 1:44 a.m.

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


      • 2
        31501357  commented on Nov. 23, 2020, 8:16 p.m.

        Apparently unordered map is too slow.