## Segment Tree Test

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Java 1.5s
Python 2.5s
Memory limit: 256M

Problem type

Xyene 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).

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 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

• commented on Feb. 4, 2021, 2:52 p.m.

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

• commented on Nov. 20, 2020, 10:06 p.m.

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

• commented on Nov. 20, 2020, 10:38 p.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.

• commented on Nov. 21, 2020, 5:29 p.m.

Oh I thought it was always constant time.

• commented on Sept. 11, 2021, 2:46 p.m.

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).

• commented on Oct. 31, 2019, 8:04 a.m.

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

• commented on Oct. 31, 2019, 10:42 a.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

• commented on Dec. 8, 2020, 4:49 p.m.

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

• commented on Dec. 8, 2020, 8:44 p.m.

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

• commented on Nov. 23, 2020, 3:16 p.m.

Apparently unordered map is too slow.

• 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?

• commented on Oct. 22, 2017, 10:56 a.m.

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

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

Why does UTSJoey's submission have 0 bytes?

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

it's probably a bug