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.
The Main Idea
Let's assume that the intervals are given first offline, then the queries are asked; Also, let's assume $$$n \le 1000$$$.
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 a path going from $$$C_1$$$ to $$$C_2 \iff L_{C_2} \le L_{C_1} \text{ and } R_{C_1} \le R_{C_2}$$$. (this condition is useful So let's name it $$$\ast$$$)
Now, we can loop over all pairs of intervals, add the edges accordingly, and find the strongly connected components of each interval.
For a query, if the intervals are in the same Scc or $$$\ast$$$ is satisfied, the answer is Yes otherwise No.
Getting rid of Scc
After a bit of thinking, you can notice that drawing unidirectional edges is useless, because of the $$$\ast$$$ we can easily get rid of them, Let's use a Union Find Tool (aka dsu), to easily manage the connected components, we will only add the bidirectional edges, and merge their components while taking care of $$$L$$$ and $$$R$$$ in the merging process.
