\(2\) 番目のクエリを処理するには「 \(x\) 超過で最小の切られた地点」「 \(x\) 未満で最大の切られた地点」の 2 つの要素を高速に取得できればよいです。よってこの問題を解くには次の 3 つのクエリを処理するデータ構造を使用すればよいとわかります。

• 集合 \(S\) に \(x\) を追加
• \(S\) に属する \(x\) より大きい要素のうち最小の要素を取得
• \(S\) に属する \(x\) より小さい要素のうち最大の要素を取得

このようなクエリは順序付き集合を管理することで高速に処理することができます。順序付き集合とは一定の順序を持って管理された集合のことで、この問題の場合は数値の大小によって要素を順序付けた集合を管理すればよいです。実装は一般には平衡二分探索木や B-Tree と呼ばれるデータ構造によって行われます。

主要な言語の多くでは順序付き集合が STL に存在するので上記のクエリを高速に処理することができます。たとえば C++ では std::set と呼ばれるデータ構造があり、以下に説明する方法で 上記の 3 つのクエリを (要素数を \(n\) として) すべて \(\mathrm{O}(\log n)\) で処理することができます。

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

int main() {
  // set<int> 型のオブジェクト st を生成
  set<int> st;

  // s に 3 を挿入 
  st.insert(3);
  // s に 5 を挿入
  st.insert(5);

  // 4 以上の要素のうち最小の要素のイテレータを取得
  auto it = st.lower_bound(4); 
  // it の示す要素を出力
  cout << *it << endl;  // 5 を出力
  // it の1つ前のイテレータの示す要素を出力
  cout << *prev(it) << endl; // 3 を出力
}

ただし、Python の場合は STL に順序付き集合が実装されておらず、自分で何らかのデータ構造を持ち出す必要があります。実装方法はさまざまですが、たとえば座標圧縮と Segment Tree / Fenwick Tree を利用して順序付き集合をシミュレートすればこちらもクエリ \(1\) 回あたり \(\mathrm{O}(\log n)\) で解くことができます。 Python で順序付き集合を管理する方法はいくつかの個人ブログで解説がなされているので「std::set python 競プロ」などの単語で検索してみてください。 ( おすすめの方法を知っている方はユーザー解説で解説していただけると多くの方の勉強になると思います。 )

以上の方法によりこの問題を \(\mathrm{O}(Q \log Q)\) で解くことができました。
別解として、 ABC214-D : Sum of Max と同様にクエリを逆から見て切られた状態から Union-Find で結合していく方法もあります。また、 Van Emde Boas tree や Y-fast trie などの高度なデータ構造を使用することで \(\mathrm{O}(Q \log \log \max(x))\) で解くこともできます。