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

P1. $$$\mathcal{O}((n+q)\log n)$$$, offlineSolutionCan be solved offline in $$$\mathcal{O}((n+q)\log n)$$$ using segment tree (just scale segment endpoints or use implicit segment tree). Sort queries by their starting endpoints (break ties arbitrarily). Let $$$a$$$ be an array (initially filled with zeros). For every segment $$$(l_i, r_i)$$$ increment $$$a_{r_i}$$$ by 1. Now, iterate through queries. You start at point $$$1$$$. In order to answer queries for segments $$$(1, r_i)$$$ you need to find sum $$$a_1+a_2+\dots+a_{r_i}$$$ (which can be done in $$$\mathcal{O}(\log n)$$$ using segment tree). Then, let's say there was a segment starting at $$$1$$$ and ending in some $$$r_i$$$. Obviously, it will never be in an answer to any other query, thus we can easily erase it (decrement $$$a_{r_i}$$$ by 1). Every segment will be added and removed only once thus final complexity is $$$\mathcal{O}((n+q)\log n)$$$

P2(and alsoP3actually). $$$\mathcal{O}((n+q)\log^2 n)$$$, offlineSolutionLet's take all segments and sort them by their left endpoint (break ties arbitrarily, scale them before). Now, take all segments (sorted) and create an array $$$a$$$ where $$$a_i = r_i$$$ (i.e. $$$i$$$-th element of this array corresponds to right endpoint of $$$i$$$-th segment in sorted order). Given a query $$$(l, r)$$$ we need to binary search on segments to find first segment with $$$l \leq l_i$$$ (Let's say it is $$$x$$$-th segment). The problem thus reduces to finding the number of elements less than or equal to $$$r$$$ on suffix $$$(x, \dots)$$$. You can use Wavelet tree to do the job in $$$\mathcal{O}(\log^2 n)$$$ per query so final complexity is $$$\mathcal{O}((n+q)\log^2 n)$$$.

PS. (Maybe there is a way to exploit the fact that we are doing queries on suffixes and not intervals, but I cannot think of anything clever right now).

P1-P3 can all be solved online with an ordered set on a segtree. I believe 1, 2, 3, 4, 7, 8, 9 can all be solved using 2d segtree

Problem 6Problem 6The problem:for each query, find the number offixedpaths nested in thequeriedpath.Let's run Euler tour of the tree and record for each node $$$v$$$ the time we entered it $$$(tin[v])$$$ and the time we left it $$$(tout[v])$$$. Consider a fixed path $$$(u, v)$$$, where $$$tin[u] < tin[v]$$$ (I assume $$$u ≠ v$$$ for any fixed path).

There are 2 cases:

Case 1.$$$u$$$ is not an ancestor of $$$v$$$ (i.e. $$$LCA(u, v) ≠ u$$$). Then, any queried path that contains $$$(u, v)$$$ must start in the subtree of $$$u$$$ and end in the subtree of $$$v$$$. Note that for any node $$$x$$$ in the subtree of $$$u$$$, $$$tin[x] ∈ [tin[u], tout[u]]$$$. So $$$(u, v)$$$ will be nested in the queried path $$$(x, y)$$$ iff $$$tin[x] ∈ [tin[u], tout[u]]$$$ and $$$tin[y] ∈ [tin[v], tout[v]]$$$ or vice versa.Case 2.$$$u$$$ is an ancestor of $$$v$$$ (i.e. $$$LCA(u, v) = u$$$). Let $$$w$$$ be the highest ancestor of $$$v$$$ below $$$u$$$. $$$w$$$ can be found using binary lifting in $$$O(log \;n)$$$ per path ($$$O(n \; log \; n)$$$ pre-processing is needed). It is easy to see that a queried path contains $$$(u, v)$$$ iff it starts in the subtree of $$$v$$$ and ends outside the subtree of $$$w$$$. So $$$(u, v)$$$ will be nested in the queried path $$$(x, y)$$$ iff $$$tin[x] ∈ [tin[v], tout[v]]$$$ and $$$tin[y] ∈ [0, tin[w] - 1] ∪ [tout[w] + 1, 2n - 1] $$$ or vice versa.Any

queriedpath $$$(x, y)$$$ can be represented as a point with coordinates $$$(tin[x], tin[y])$$$. Then, anyfixedpath creates 1 or 2 ranges for both coordinates, effectively making 1 or 2 rectangles on the plane. The answer to the query is the number of rectangles containing the queried point. This quite classical problem can be solved off-line using a difference array and a Fenwick tree in $$$O(q \; log \; n)$$$. So the total time complexity of the solution is $$$O((n + q) \; log \; n)$$$ and memory is $$$O(n \; log \;n)$$$. However, memory is $$$O(n \; log \; n)$$$ just because of the binary lifting construction, which is needed to find $$$w$$$. This subproblem is just a Level Ancestor problem and can be easily solved off-line in $$$O(n + q)$$$, e.g. by maintaining a vector of nodes on the path from the root to each vertex, so the needed $$$w$$$ can be accessed by a single array index in $$$O(1)$$$. This optimization would reduce memory complexity to $$$O(n)$$$.See the code of the unoptimized $$$O((n + q) \; log \; n)$$$ solution below:

Code