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.
Note: in this editorial, it's assumed that the interval's ranges don't exceed $$$2n$$$, you can get the queries offline and compress the intervals.
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. The query handling is similar.
$$$n \le 10^5$$$
Note: this is just the magic of data structures, specifically segment trees.
Let's use a segment tree to handle component merging faster. In the segment tree nodes, we store a list of leaders of the DSU components where they strictly contain the range of this node.
Let's assume that we're adding the interval $$$[l, r]$$$, due to the length strictly increasing nature, we can trace the path of $$$l$$$ from the segment tree root to the leaf, and merge the current interval's component with the components store in the nodes of the path, we do the same for $$$r$$$.
Let the component of the current interval be $$$C$$$ after merging, now we must add this component to the nodes of $$$(L_C, R_C)$$$ range in the segment tree; so the other intervals can merge with the current interval.
Also note that while adding the interval $$$[l, r]$$$, after passing through a node, we'll clear its list of leaders.
The query handling is the same.
The full solution
Now it's just left to put the puzzle pieces together. First, we'll Get all the queries offline, So we can compress the intervals.
Now let's iterate through the queries, if the current query is an addition query, we'll just replace $$$[l, r]$$$ with their compressed equivalent, and add the interval using the previously mentioned technique with a segment tree.
Otherwise: If the intervals were in the same component, or $$$\ast$$$ was satisfied, output Yes, otherwise No.
Code
Thanks for your time, I hope it was useful.
this was mainly a challenge for me, to formalize my solution.
A Question
What if the interval lengths weren't necessarily increasing? Now what.
Since the main reason this solution works, is that we're guaranteed that after an interval is added, there won't be any interval added which will be completely inside of it, because it'll create a bidirectional edge between them which is incorrect.
