题意

我们有 $N$ 个套娃，每个套娃有直径 $R_i$ 和高度 $H_i$。套娃 $i$ 能套住套娃 $j$ 当且仅当：

对于每个查询 $(A, B)$，我们考虑所有满足条件的套娃：

在这些套娃中，我们要通过嵌套使得没有被套的套娃数量最小。

关键理论：Dilworth 定理

Dilworth 定理：在任意有限偏序集中，最小链覆盖数等于最大反链大小。

在这里：

• 链：一个嵌套序列（每个可以套住下一个）
• 链覆盖：一组链，覆盖所有套娃
• 反链：任意两个套娃都不能嵌套（即不可比较）

因此：

而最小链覆盖数就是我们要的"没有被套的套娃最小数量"。

问题转化

对于查询 $(A, B)$，设满足条件的套娃集合为 $S$，则：

在二维偏序中，最大反链可以通过以下方法求得：

方法：按一维排序，对另一维求 LIS

将套娃按直径 $R$ 降序排序，对于直径相同的按高度 $H$ 升序排序，然后对高度序列求最长严格下降子序列的长度。

或者等价地： 将套娃按高度 $H$ 升序排序，对于高度相同的按直径 $R$ 降序排序，然后对直径序列求最长严格下降子序列的长度。

算法思路

步骤 1：预处理所有套娃

1. 读入所有套娃的 $(R_i, H_i)$
2. 离散化 $R$ 和 $H$ 坐标（因为值域达到 $10^9$）

步骤 2：离线处理查询

1. 读入所有查询 $(A_i, B_i)$
2. 将查询按 $A$ 降序排序
3. 将套娃按 $R$ 降序排序

步骤 3：扫描线 + 树状数组

按 $A$ 从大到小处理查询：

• 将满足 $R \geq A$ 的套娃加入数据结构
• 在数据结构中维护高度维的信息
• 查询当前集合的最大反链大小

实际上，在嵌套关系中：

• 每个链对应一个嵌套序列
• 最小链覆盖数就是最终露在外面的套娃数量
• 这就是我们要求的答案

根据 Dilworth 定理：

但是最大反链大小就是在排序后的高度序列中求最长非递增子序列的长度！

所以正确的做法是：对排序后的高度序列求最长非递增子序列的长度，这就是答案。

复杂度分析

• 排序：$O(N \log N + Q \log Q)$
• 离散化：$O((N+Q) \log (N+Q))$
• 扫描线：$O((N+Q) \log N)$
• 总复杂度：$O((N+Q) \log (N+Q))$，适合 $N, Q \leq 2 \times 10^5$

总结

这道题的关键在于：

1. 理解 Dilworth 定理：将问题转化为求偏序集的最大反链
2. 二维偏序处理：通过排序将二维问题转化为一维 LIS 问题
3. 离线查询：使用扫描线思想高效处理多个查询
4. 数据结构优化：用树状数组维护最长非递增子序列