P15452 [JOI 2026 SemiFinal] 宝石商 / Jeweler

JOI 君经营着一家宝石店。有 $N$ 位顾客想要购买宝石，这些顾客被编号为 $1$ 到 $N$。顾客 $i$ ($1 \le i \le N$) 可以在时刻 $L_i$ 到时刻 $R_i$ 之间的任意时刻到访店铺，并打算购买 $C_i$ 个宝石。 JOI 君很忙，无法一直开店。因此，他考虑了 $M$ 个开店时间的方案。方案被编号为 $1$ 到 $M$，方案 $j$ ($1 \le j \le M$) 是指在时刻 $S_j - 0.1$ 到时刻 $T_j + 0.1$ 之间开店。对于每个方案，顾客 $i$ ($1 \le i \le N$) 如果在其可到访的时间段内存在店铺开门的时刻，则会到访店铺并购买 $C_i$ 个宝石。反之，如果不存在这样的时刻，顾客 $i$ 则不会到访，也不会购买宝石。但是，JOI 君的店铺里有充足的宝石，不会出现售罄的情况。 给定 JOI 君店铺的顾客信息以及开店时间的各个方案，请编写一个程序，针对每个方案求出总共能卖出多少个宝石。

输入从标准输入中以以下格式给出： $N$ $L_1\ R_1\ C_1$ $L_2\ R_2\ C_2$ $\vdots$ $L_N\ R_N\ C_N$ $M$ $S_1\ T_1$ $S_2\ T_2$ $\vdots$ $S_M\ T_M$

向标准输出输出 $M$ 行。第 $j$ 行 ($1 \le j \le M$) 输出方案 $j$ 中总共能卖出的宝石个数。

#### 样例解释 1 方案 1 中，从时刻 $3.9$ 到时刻 $6.1$ 开店。顾客 1 可在时刻 $4$，顾客 2 可在时刻 $5$，顾客 3 可在时刻 $6$ 到店铺购买宝石，总共卖出 $10 + 20 + 30 = 60$ 个宝石。 方案 2 中，从时刻 $0.9$ 到时刻 $2.1$ 开店。任何顾客都无法在开店时刻到访，因此总共卖出 $0$ 个宝石。 方案 3 中，从时刻 $5.9$ 到时刻 $8.1$ 开店。顾客 2 和顾客 3 均可在时刻 $7$ 到店铺购买宝石，总共卖出 $20 + 30 = 50$ 个宝石。 该输入样例满足子任务 1、5 的数据范围。 #### 样例解释 2 方案 1 中，顾客 1 和顾客 3 可以到店铺购买宝石，总共卖出 $1 + 4 = 5$ 个宝石。 方案 2 中，顾客 1、顾客 2、顾客 3 可以到店铺购买宝石，总共卖出 $1 + 2 + 4 = 7$ 个宝石。 方案 3 中，所有顾客都可以到店铺购买宝石，总共卖出 $1 + 2 + 4 + 8 = 15$ 个宝石。 该输入样例满足子任务 1、3、4、5 的数据范围。 ### 数据范围 - $1 \le N \le 300\,000$ - $1 \le L_i < R_i \le 1\,000\,000$ ($1 \le i \le N$) - $1 \le C_i \le 10^9$ ($1 \le i \le N$) - $1 \le M \le 300\,000$ - $1 \le S_j \le T_j \le 1\,000\,000$ ($1 \le j \le M$) - 输入的所有值均为整数。 ### 子任务 1. (12 分) $N \le 1000,\ M \le 1000$ 2. (17 分) $S_j = T_j$ ($1 \le j \le M$) 3. (21 分) $S_j = 1$ ($1 \le j \le M$) 4. (23 分) $S_j \le S_{j+1},\ T_j \le T_{j+1}$ ($1 \le j < M$) 5. (27 分) 无额外限制。 翻译由 DeepSeek 完成