Segment Tree Test

Points: 15 (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 $N$ ~N~ $(1 \le N \le 100\,000)$ ~(1 \le N \le 100\,000)~ elements, indexed from $1$ ~1~ to $N$ ~N~. There are $M$ ~M~ $(1 \le M \le 500\,000)$ ~(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$ ~x~-th element of the array to $v$ ~v~.
M l r Output the minimum of all the elements from the $l$ ~l~-th to the $r$ ~r~-th index, inclusive.
G l r Output the greatest common divisor of all the elements from the $l$ ~l~-th to the $r$ ~r~-th index, inclusive.
Q l r Let $G$ ~G~ be the result of the operation G l r right now. Output the number of elements from the $l$ ~l~-th to the $r$ ~r~-th index, inclusive, that are equal to $G$ ~G~.

At any time, every element in the array is between $1$ ~1~ and $10^9$ ~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$ ~N~ and $M$ ~M~.

The second line has $N$ ~N~ integers, the original array.

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

Sample Output 1

2
4
2

Sample Input 2

Sample Output 2

2
3

Comments

17

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

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

1

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.

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

0

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

My solution is $O(QlogN)$ ~O(QlogN)~ 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.