这道题目选取了高中化学必修二《有机化学基础》或选修《有机化学》中关于 “石油的分馏”（Fractional Distillation）的知识点。

题目模型是经典的排序（Sorting）结合二分查找（Binary Search），难度定位 GESP 5级（CSP-J T2/T3），主要考察对有序数据的处理能力。

---

题目：石油分馏模拟系统 (Petroleum Fractionation Simulation)

【背景知识讲解】

在高中化学中，我们知道石油（Crude Oil）是一种成分非常复杂的混合物，主要含有各种烷烃、环烷烃和芳香烃。 不同烃类分子的碳原子数不同，导致它们的 沸点（Boiling Point） 也不同：

• 碳原子数越少，分子间作用力越小，沸点越低（如甲烷、乙烷是气体）。
• 碳原子数越多，分子间作用力越大，沸点越高（如沥青是固体）。

分馏（Fractionation） 是利用混合物中各组分沸点不同，通过控制温度范围，将它们分离成不同“馏分”的过程。 例如：

• 温度范围 $< 40^\circ \text{C}$：得到石油气。
• 温度范围 $40 \sim 200^\circ \text{C}$：得到汽油。
• 温度范围 $200 \sim 350^\circ \text{C}$：得到柴油等。

【题目描述】

你是一名炼油厂的工程师，负责控制巨大的分馏塔。 实验室分析出了当前批次原油中含有的 $N$ 种主要烃类物质。对于每种物质，我们知道了它的名称（字符串）和沸点（整数，单位 $^\circ \text{C}$）。

炼油厂接到了 $M$ 个客户的订单，每个订单都需要提取特定沸点范围 $[L, R]$ 内的所有物质（包含边界 $L$ 和 $R$）。

为了提高效率，请你编写一个程序：

1. 整理所有烃类物质，按沸点从低到高排序（如果沸点相同，按名称字典序从小到大排序）。
2. 对于每个订单给出的温度区间 $[L, R]$，快速计算出该区间内包含多少种物质，并输出其中沸点最低的那种物质的名称。

注意：

• 如果某个区间内没有物质，输出 0 和 None。
• 题目保证沸点数据和查询范围均为整数。

【输入格式】

第一行包含一个整数 $N$，表示烃类物质的数量。 接下来 $N$ 行，每行包含一个字符串 $S_i$ 和一个整数 $B_i$，表示物质的名称和沸点。 第 $N+2$ 行包含一个整数 $M$，表示订单（查询）的数量。 接下来 $M$ 行，每行包含两个整数 $L_j, R_j$，表示第 $j$ 个订单需要的沸点范围。

【输出格式】

对于每个订单，输出一行，包含两个信息（中间用空格隔开）：

1. 该范围内物质的数量。
2. 该范围内沸点最低的物质名称（如果数量为 0，输出 None）。

【样例数据】

输入：

5
Methane -161
Butane -1
Octane 125
Decane 174
Ethane -89
3
-200 -50
-100 0
100 200

输出：

2 Methane
2 Ethane
2 Octane

样例解释：

1. 排序：首先对物质按沸点排序：
   • Methane (-161)
   • Ethane (-89)
   • Butane (-1)
   • Octane (125)
   • Decane (174)
2. 查询 1 [-200, -50]: 包含 Methane(-161) 和 Ethane(-89)。共 2 个。最低的是 Methane。
3. 查询 2 [-100, 0]: 包含 Ethane(-89) 和 Butane(-1)。共 2 个。最低的是 Ethane。
4. 查询 3 [100, 200]: 包含 Octane(125) 和 Decane(174)。共 2 个。最低的是 Octane。

【数据范围】

• 对于 100% 的数据：$1 \le N, M \le 100,000$。
• 沸点 $B_i$ 及查询边界 $L, R$ 在 $[-273, 1000]$ 范围内。
• 名称字符串长度不超过 20，仅含英文字母。

---

一、 思路提示

1. 数据的有序化：

   • 题目要求在一个范围内查找。如果数据是乱序的，每次查询都要遍历 $N$ 个元素，总复杂度是 $O(N \times M)$。
   • 当 $N, M = 10^5$ 时，运算量达到 $10^{10}$，这会超时（Time Limit Exceeded）。
   • 关键策略：先将所有物质按照沸点进行排序（Sorting）。

2. 查找的加速：

   • 排序后，沸点满足 $[L, R]$ 的物质在数组中一定是连续的一段。
   • 我们需要找到：
     • 第一个沸点 $\ge L$ 的位置（区间的起点）。
     • 第一个沸点 $> R$ 的位置（区间的终点之后）。
   • 在一个有序数组中查找特定值的位置，最快的方法是二分查找（Binary Search）。

3. 标准库的利用：

   • C++ 的 <algorithm> 库提供了非常好用的二分查找函数：
     • std::lower_bound(begin, end, val): 查找第一个 $\ge val$ 的元素迭代器。
     • std::upper_bound(begin, end, val): 查找第一个 $> val$ 的元素迭代器。
   • 利用这两个函数，可以在 $O(\log N)$ 的时间内处理每一个查询。

---

二、 预备知识点总结

1. 结构体（Struct）：将名称和沸点打包存储。
2. 排序（Sorting）：std::sort 以及自定义比较函数（Comparator）。
3. 二分查找（Binary Search）：lower_bound 和 upper_bound 的理解与使用。
4. 时间复杂度：理解为什么 $O(M \log N)$ 优于 $O(MN)$。

---

三、 启发式教学：草稿纸上的推理过程

教练：“想象一下，仓库里乱七八糟地堆着几万瓶化学试剂。现在老板让你把沸点在 100 到 200 度的都挑出来。如果你一瓶瓶看，是不是累死了？”

学生：“是的，太慢了。”

教练：“那第一步我们该做什么？”

学生：“把它们按沸点从低到高排好队放在架子上！”

教练：“非常好。现在架子上的试剂沸点是这样的（画数轴）：” ... -161(M), -89(E), -1(B), 125(O), 174(D) ...

教练：“现在查询区间是 [-100, 0]。我们不需要从头数。我们只要找到两个‘切割点’。”

1. 左刀：我们要找第一个 $\ge -100$ 的位置。
   • 看中间：-1。比 -100 大。往左找。
   • 看左边：-161。比 -100 小。往右找。
   • 找到了 -> -89 (Ethane)。这是起跑线。
2. 右刀：我们要找第一个 $> 0$ 的位置（因为包含 0，所以我们要找大于 0 的才算越界）。
   • 找到了 -> 125 (Octane)。这是终点线外面。

教练：“起跑线是下标 1，终点线外是下标 3。那么在这个范围内的数量就是 $3 - 1 = 2$ 个。它们分别是下标 1 和 下标 2。沸点最低的就是起跑线那个——下标 1 (Ethane)。”

总结算法：

1. sort。
2. lower_bound 找 $L$。
3. upper_bound 找 $R$。
4. 算距离，输出。

---

四、 读题关键词总结

1. “快速计算” / $N, M = 10^5$ $\rightarrow$ 暗示 $O(N \log N)$ 算法，必用二分或高级数据结构。
2. “按沸点排序” $\rightarrow$ 提示解题的第一步。
3. “沸点最低的名称” $\rightarrow$ 排序后，区间内的第一个元素就是沸点最低的。

---

五、 标准题解代码 (C++14)

见题解

这道题目将石油分馏的化学知识与排序、二分查找的算法知识完美融合。它直观地展示了为什么要对数据进行排序（为了分馏），以及如何高效地在有序数据中截取片段（二分），非常适合作为 GESP 5 级的训练题。