Hello Codeforces community, This is an editorial for an 11-year-old problem in CF, and the official editorial still has it TODO, so yeah, why not?
I'll use step-by-step guides to demonstrate the path to finding the solution to this problem, and I hope it will be helpful to other people.
1. The intervals are given offline.
In this subtask, let's assume that the intervals are given to us, and the queries are asked after all the intervals are given.
1.1. $$$n \le 1000$$$
Note: this is the whole intuition behind the main solution.
Let's us define an edge from interval $$$i$$$ to $$$j$$$ bidirectional when $$$i$$$, $$$j$$$ intersect but none of which contains the other(e.g. [1, 10] and [5, 15]).
And an edge unidirectional from $$$i$$$ to $$$j$$$ when $$$i$$$ is contained within $$$j$$$.
Now we can use 2 unidirectional edges to form a bidirectional edge.
We draw a unidirectional edge from interval $$$i$$$ to $$$j$$$, when we can directly get to $$$j$$$ from $$$i$$$. Let this graph be $$$G$$$. Take an Scc from $$$G$$$, $$$C$$$. What we can notice in this graph is that there is a path between all pairs of vertices in $$$C$$$. So let's condensate the Sccs into single vertices and create the condensation graph. Let $$$L_C$$$ be the minimum l in all of the intervals of $$$C$$$, $$$R_C$$$ is similarly defined.
Due to intervals lengths being strictly increasing(The whole reason this solution works), We can notice that for 2 Sccs, $$$C_1$$$ and $$$C_2$$$, there is an edge going from $$$C_1$$$ to $$$C_2 \iff L_{C_2} \le L_{C_1} \text{ and } R_{C_1} \le R_{C_2}$$$
