ABC174F

https://gyazo.com/d1e4ee6d9ee7b595405a406cf1c6fbe7

Thoughts.

If it can be determined in logarithmic order whether or not color ci exists within the range, it can be done in time.

dichotomous search

mounting

7 minutes to implement, submit, TLE

Oh, not at all, even if we can determine if each color is in range in logarithmic order for every N cases, it's O(QNlogN).

Consideration again

Still the worst O(QN).

Make a set of ball colors every 2^n blocks.

The total number of sets is 2N-1

A set of colors for the requested interval can be created by merging logN times.

But if you do it normally, the merge is heavy and you end up with O(QN).

Official Explanation

Interval queries are segment trees, but merging is heavy

Maintain the "rightmost sphere location" of each color at each point in time.

If this is greater than L, then the color is in the range, constant order

But this is still O(QN)

Put the "rightmost sphere location" of each color into the [Fennic tree

Counting the number of pieces is logarithmic order in the range sum

I see, so this is the point.

3TLE

ARC174F

---