解题思路
把每项工程看成平面上的点 (li,ri)。查询窗口 [l,r] 要求 li≥l 且 ri≤r,即统计矩形 [l,+∞)×(−∞,r] 中的点数。这是二维偏序计数。
离线处理:
- 将所有工程按 ri 升序排序,所有查询按 r 升序排序。
- 依次处理查询的右端点,把所有满足 ri≤r 的工程加入数据结构。
- 数据结构只维护 li 这一维:当前已加入的点里,li≥l 的数量。对所有 li 做坐标压缩,用树状数组在对应位置加
1。设已加入 k 个点,令 idx 为不小于 l 的最小压缩下标,则答案为 k 减去压缩坐标小于 idx 的前缀和。