显然答案是最大的 $x$ 满足 $< x$ 的数至少有 $x$ 个。直接莫队 + 线段树即可 $O(n\sqrt n\log n)$。

考虑从大到小枚举答案 $x$，维护询问的每个区间中 $< x$ 的个数。每次询问最大值并删除对应询问，直到个数小于 $x$ 为止。

然而最大值很难维护，因为修改相当于矩形加法 (当然你可以用 K-D Tree)。但对于两个询问区间 $S_1$, $S_2$，若 $S_1$ 包含 $S_2$，则 $S_1$ 的答案不小于 $S_2$。所以我们只需要维护当前不被包含的区间。如果将所有区间按左端点排序就只需要区间加法，可以用线段树维护。删除一个区间后，要加入所有新的极大区间，这也可以用线段树维护。加入区间时要查询 $< x$ 的数个数，用树状数组维护即可。

时间复杂度 $O((n+q)\log (n+q))$。