Segment Queries

CodeChefRating 2679Open on judge ↗

Consider a 1D-grid with N points, numbered 1, 2, ..., N from left to right. The segment is denoted by a pair [L, R] and contains all the points with the indices between L and R inclusively. Some of the points can be marked. Initially all the points are unmarked. Sergey wants to develop a data structure that would help him to answer the following two types of queries efficiently on the segments

HINT LADDERno hints yet

L1 Observation

L2 Technique

L3 Approach

L4 Pseudo-code

🔒

L5 Full solution

L5 unlocks only if you insist twice

solution.cppC++17

CodeSearch Tutor

Hints, not spoilers — it won’t hand over the full solution unless you insist.

voice by Sarvam AI