In order to process the second type of query, it is sufficient to find the following two values: “the minimum coordinates greater than \(x\) that has been cut” and “the maximum coordinates less than \(x\) that has been cut.” Therefore, in order solve this problem, we want a data structure that processes the following three queries:

• Add \(x\) to a set \(S\)
• Find the minimum element in \(S\) that is greater than \(x\)
• Find the maximum element in \(S\) that is less than \(x\)

Such queries can be processed fast by managing an ordered set. An ordered set is a set in which the elements are stored in a certain order. For this problem, it is sufficient to manage a set in which its elements are ordered by which element is greater. They are generally implemented by means of data structures called self-balancing binary search tree or B-Tree.

Many languages have ordered set in their standard library, which processes the queries above fast. For example, in C++, there is a data structure called std::set, which processes the three kinds of queries mentioned above in an \(\mathrm{O}(\log n)\) time (where \(n\) is the number of elements).

#include <iostream>
#include <set>
using namespace std;

int main() {
  // create an object st of type set<int>
  set<int> st;

  // Insert 3 to st
  st.insert(3);
  // Insert 5 to st
  st.insert(5);

  // Obtain an iterator to the minimum element greater than or equal to 4
  auto it = st.lower_bound(4); 
  // Output the element pointed by "it"
  cout << *it << endl;  // Outputs 5
  // Output the element pointed by the previous iterator of "it"
  cout << *prev(it) << endl; // Outputs 3
}

Note that Python does not have ordered set in its standard library, and therefore you have to prepare some data structure on your own. There are many ways to implement it. For example, one can simulate an ordered set with coordinates compression and Segment Tree / Fenwick Tree, so that each query is processed in an \(\mathrm{O}(\log n)\) time. There are some editorials online of how to implement an ordered set in Python, which can be find with keywords like “std::set python.” (If you know a good way, it would be helpful for many users to explain it as a user’s editorial.)

Therefore, the problem has been solved in a total of \(\mathrm{O}(Q \log Q)\) time.
As another way to solve it, one can inspect the queries in the reverse order and merge them with Union-Find, just as in ABC214-D : Sum of Max. Also, one can solve this problem in a total of \(\mathrm{O}(Q \log \log \max(x))\) with an advanced data structures like Van Emde Boas tree or Y-fast trie.