You may recognize similarities with the problem Enchanted Forest from the 2014 Chinese National Olympiad in Informatics.

Subtask 1

For the first subtask, we can construct a graph for each query using only edges with ~d_i \ge x_j~ and ~t_i \le y_j~, and determining if the graph is connected. This can be done in many ways such as breadth first search, depth first search, or the Union-Find data structure.

Time Complexity: ~\mathcal{O}(Q \cdot (N + M))~ or ~\mathcal{O}(Q \cdot (N + M \cdot \alpha(N)))~

Subtask 2

For the second subtask, we can make the observation that for each unique value of ~d_i~, there will be a minimum value of ~y_j~ where the graph is completely connected. In fact, as ~d_i~ decreases, the minimum value of ~y_j~ decreases. In order to find this minimum value of ~y_j~ for each ~d_i~, we need to find a minimum bottleneck spanning tree, which can be done by constructing a minimum spanning tree with all edges with a durability of at least ~d_i~, where the weight of each edge is ~t_i~. The minimum value of ~y_j~ is equal to the maximum value of ~t_i~ in the minimum spanning tree (assuming a tree exists). If the edges are presorted by ~t_i~, this can be done in ~\mathcal{O}(N + M \cdot \alpha(N))~ time using Kruskal's algorithm. To answer the queries, we can binary search for the smallest value ~d_i~ where ~d_i \ge x_j~ and use the precomputed answer for that value. Alternatively, a two pointer approach can be used the answer the queries offline.

Time Complexity: ~\mathcal{O}(M \cdot (N + M \cdot \alpha(N)) + Q \log M)~

Subtask 3

When edges are being added to the graph in decreasing order of ~d_i~, we can maintain the minimum spanning tree efficiently. When an edge is added to the previous minimum spanning tree, it will create some cycle. If the edge with the maximum edge weight is deleted from this cycle, then we will obtain the new minimum spanning tree. We can find this edge using a Link-Cut Tree with ~N + M~ nodes where the value of the first ~N~ nodes are ~-\infty~ and the value of the ~(N + i)^{th}~ node is ~t_i~ representing the ~i^{th}~ edge (we can imagine this as a node in the middle of an edge). We can query for the maximum edge using this data structure, while also maintaining a set of the edge weights in the minimum spanning tree in order to answer queries in a similar manner as subtask ~2~.

Time Complexity: ~\mathcal{O}((N + M) \log(N + M) + Q \log M)~

There exist other solutions such as square root decomposition, and divide and conquer.