题解：P15452 [JOI 2026 SemiFinal] 宝石商 / Jeweler
wrong_accept · · 题解
思路
-
顾客能来的条件。
顾客
i 能来\iff [l_i, r_i] \cap [s_j, t_j] \neq \emptyset \iff l_i \le t_j 且r_i \ge s_j 。 -
答案公式。
-
步骤。
- 第一步：按
l_i 排序顾客，按t_j 排序查询。双指针维护l_i \le t_j 的顾客，加入树状数组\Rightarrow 得到\text{sum1}[j] = \sum_{l_i \le t_j} c_i 。 - 第二步：按
r_i 排序顾客，按s_j 排序查询。双指针维护r_i < s_j 的顾客，加入树状数组。 - 第三步：
\text{ans}[j] = \text{sum1}[j] - \text{sum2}[j] 。
- 第一步：按
-
复杂度。
时间复杂度
O((N+M) \log N) 。