Gates to Another World
Contest: Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 3300
Tags: bitmasks, data structures, dsu, two pointers

As mentioned previously William really likes playing video games. In one of his favorite games, the player character is in a universe where every planet is designated by a binary number from $$$0$$$ to $$$2^n - 1$$$. On each planet, there are gates that allow the player to move from planet $$$i$$$ to planet $$$j$$$ if the binary representations of $$$i$$$ and $$$j$$$ differ in exactly one bit.

William wants to test you and see how you can handle processing the following queries in this game universe:

- Destroy planets with numbers from $$$l$$$ to $$$r$$$ inclusively. These planets cannot be moved to anymore.
- Figure out if it is possible to reach planet $$$b$$$ from planet $$$a$$$ using some number of planetary gates. It is guaranteed that the planets $$$a$$$ and $$$b$$$ are not destroyed.

Input format:
The first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 50$$$, $$$1 \leq m \leq 5 \cdot 10^4$$$), which are the number of bits in binary representation of each planets' designation and the number of queries, respectively.

Each of the next $$$m$$$ lines contains a query of two types:

block l r — query for destruction of planets with numbers from $$$l$$$ to $$$r$$$ inclusively ($$$0 \le l \le r < 2^n$$$). It's guaranteed that no planet will be destroyed twice.

ask a b — query for reachability between planets $$$a$$$ and $$$b$$$ ($$$0 \le a, b < 2^n$$$). It's guaranteed that planets $$$a$$$ and $$$b$$$ hasn't been destroyed yet.

Output format:
For each query of type ask you must output "1" in a new line, if it is possible to reach planet $$$b$$$ from planet $$$a$$$ and "0" otherwise (without quotation marks).

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Note:
The first example test can be visualized in the following way:

Response to a query ask 0 7 is positive.

Next after query block 3 6 the graph will look the following way (destroyed vertices are highlighted):

Response to a query ask 0 7 is negative, since any path from vertex $$$0$$$ to vertex $$$7$$$ must go through one of the destroyed vertices.

Example input:
3 3
ask 0 7
block 3 6
ask 0 7

Example output:
1
0

Example input:
6 10
block 12 26
ask 44 63
block 32 46
ask 1 54
block 27 30
ask 10 31
ask 11 31
ask 49 31
block 31 31
ask 2 51

Example output:
1
1
0
0
1
0

Editorial:
Let's change the formulation of the problem: we will execute queries in reverse order, and assign a lifetime to each segment of blocked vertices. Lifetime — until what moment the segment is blocked. Note, if we look through the requests in reverse order, then for each segment it is possible to determine the moment of time after which the vertices from this segment cease to be blocked.
Thus, the problem looks like this: given a graph that is an $$$n$$$-dimensional hypercube (each vertex has $$$n$$$ edges to adjacent vertices that differ from it by only one coordinate), and there are $$$m$$$ blocked vertex segments $$$[l_i \dots r_i]$$$ that live up to the time $$$t_i$$$.
Consider the following fact:
If we take an $$$n$$$-dimensional hypercube and sequences of vertices $$$0, 1, \dots, 2^{n-1} - 1$$$ and $$$2^{n-1}, 2^{n-1} + 1, \dots, 2^{n} - 1$$$, then the numbers in the corresponding positions from these two sequences are neighbours to each other, since they differ only in the most significant bit, that is, in the $$$ 2^{n-1}$$$ bit. For a better understanding, let's depict this for $$$n = 4$$$:
• $$$ 0000 - 1000 $$$
• $$$ 0001 - 1001 $$$
• $$$ 0010 - 1010 $$$
• $$$ 0011 - 1011 $$$
• $$$ 0100 - 1100 $$$
• $$$ 0101 - 1101 $$$
• $$$ 0110 - 1110 $$$
• $$$ 0111 - 1111 $$$
Here $$$a - b$$$ denotes that $$$a$$$ is a neighbour of $$$b$$$, and $$$a$$$ is present in the first sequence, and $$$b$$$ in the second.
For simplicity, we will only prohibit movement between a blocked vertex and an unblocked one. Let's learn how to get a "compressed" graph, each vertex of which would represent a connected subset of the vertices of the hypercube. Also, this set, which represents a vertex, is a set of consecutive vertices, that is, it is a segment. On each edge of this graph is written the time — when this edge begins to exist. Time makes sense, since an edge can be drawn between a vertex that represents a set of blocked vertices and a vertex that represents a set of unblocked vertices. And the time on this edge there will be a moment in time when the set of vertices is unblocked. Recall that now we are solving a problem in which the vertices are blocked until a certain moment in time. The answer to the reachability request is the reachability request for a given "compressed" graph. It is only necessary to correctly determine the reachability of which two vertices of the "compressed" graph we are interested in.
Let's learn how to recursively build a given compressed graph.
Input data for the construction of this graph are: $$$n$$$ — the dimension of the hypercube, $$$S = \{ (l_i, r_i) \}$$$ — the set of blocked vertices. If there are no segments worth blocking, then the compressed graph is one vertex, which is responsible for the connected set $$$ \{0, 1, 2, \dots, 2^{n} - 1 \}$$$ of hypercube vertices. If there is one segment $$$(l_i, r_i) = (0, 2^{n} - 1)$$$, then the compressed graph is one vertex representing all vertices, and they are all blocked.
Otherwise, we can divide the hypercube into two parts: by the most significant bit. That is, into two hypercubes of dimensions $$$2^{n-1}$$$. And each segment $$$l_i, r_i$$$ can go further, as input, either into two hypercubes, or into one of them. Having received compressed graphs from each of the two hypercubes, we can match the adjacent vertices of these hypercubes, as illustrated above.
It is not difficult to combine two such graphs, since each vertex of the graph describes the set of vertices of the hypercube, and this set is a segment, therefore, if we have the vertices of the first and second graphs, $$$V_1$$$ and $$$V_2$$$, respectively, in ascending order of the segments for which they answer, then it is possible to combine these two graphs in $$$O(|V_1| + |V_2|)$$$ time, and create no more than $$$O(|V_1| + |V_2|)$$$ edges and obtain a new graph of size $$$|V_1| + |V_2|$$$.
In total, the resulting graph will have a size of $$$n \times m$$$, and the final asymptotics will be $$$O(n^2 \times m \times ACK)$$$, where $$$ACK$$$ is the cost of the operation in the DSU. The DSU is needed to pass queries in reverse order and connect the edges at the right times when the edges begin to exist.
The asymptotics is as follows, since each vertex of the graph may go through all $$$n$$$ layers of recursion (as you may have noticed, the solution procedure resembles divide and conquer) and at the same time create a new edge in each layer. And the graph has such a size, since each blocked segment in this procedure can be split into $$$n$$$ segments.
For a better understanding, see the author's solution.