Hello, Codeforces!
Recently I was solving problems on data structures from the archive, and I came up with ideas for several problems. I would like to share them with you and get your opinion on them. This blog is indirectly inspired by similar blog by BERNARD. I will also be very happy if you suggest solutions to problems (faster than $$$O(nq)$$$) or their modifications in the comments. Any feedback is very important!
Anyways, let's move on to the tasks.
Problem 1. There is a set of $$$n$$$ segments given by the boundaries $$$l_i$$$ and $$$r_i$$$ ($$$0$$$ <= $$$l_i$$$ <= $$$r_i$$$ <= $$$10^9$$$). There are also $$$q$$$ queries, each defined by a segment with boundaries $$$x_i$$$ и $$$y_i$$$ ($$$0$$$ <= $$$x_i$$$ <= $$$y_i$$$ <= $$$10^9$$$). For each query, you need to find the number of segments nested in the query segment.
Problem 2. Similar to problem 1, but there are queries of adding segments to the set.
Problem 3. Similar to problem 2, but there are queries of removing segments from the set (it is guaranteed that the segment to be removed is in the set).
Problem 4. Similar to problem 2, but after adding a segment, a new version of the set is created and you need to answer online queries for a specific version of the set.
Problem 5. Similar to problem 1, but in 2D/kD (i.e. the set consists of rectangles on the plane, you need to find the number of rectangles on the query rectangle).
Problem 6. Similar to problem 1, but instead of segments we will use simple paths in the tree, it is necessary to find the number of paths nested in the query path.
Problem 7. Similar to problems 1-4, but each segment has its own weight and it is necessary to find not the number, but the minimum / maximum among the weights of the nested segments.
Problem 8. Similar to problem 7, but you need to find the number of different weights of nested segments.
Problem 9. Similar to problem 7, but you need to find the median / k-th statistics by the weights of the nested segments.
Problem 10. There is a set of $$$n$$$ segments on the coordinate plane given by two points whose coordinates do not exceed $$$10^9$$$. It is necessary to answer queries for the number of segments from the set in the rectangle.
Problem 11. Similar to problem 10, but you need to be able to perform the same operations as in problems 1-4 and 7-9.
