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