AT_joi2026_semifinal_b 宝石商 (Jeweler)

JOI 君经营着一家珠宝店。这家珠宝店有 $N$ 位打算购买珠宝的顾客，这些顾客按 $1$ 到 $N$ 编号。第 $i$ 位顾客（$1 \leq i \leq N$）可以在时刻 $L_i$ 到时刻 $R_i$ 之间的任意时刻来店里，并计划购买 $C_i$ 个珠宝。 由于 JOI 君很忙，无法一直开店。因此，他考虑了 $M$ 种开店时间的方案。每个方案编号为 $1$ 到 $M$。第 $j$ 个方案（$1 \leq j \leq M$）是指在时刻 $S_j - 0.1$ 到时刻 $T_j + 0.1$ 期间开店。对于每个方案，如果第 $i$ 位顾客（$1 \leq i \leq N$）有能到店的时刻店是开着的，就会来购买 $C_i$ 个珠宝。否则，该顾客不会来，也不会购买珠宝。假设 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 \leq j \leq M$）为第 $j$ 个方案下珠宝的总销量。

## 小提示 1. （$12$ 分）$N \leq 1\,000$，$M \leq 1\,000$。 2. （$17$ 分）$S_j = T_j$（$1 \leq j \leq M$）。 3. （$21$ 分）$S_j = 1$（$1 \leq j \leq M$）。 4. （$23$ 分）$S_j \leq S_{j+1}$，$T_j \leq T_{j+1}$（$1 \leq j < M$）。 5. （$27$ 分）无其他额外约束。 ## 样例解释 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$ 的约束。 ## 样例解释 3 该输入样例满足小提示 $1,5$ 的约束。 # 数据范围与约束 - $1 \leq N \leq 300\,000$。 - $1 \leq L_i < R_i \leq 1\,000\,000$（$1 \leq i \leq N$）。 - $1 \leq C_i \leq 10^9$（$1 \leq i \leq N$）。 - $1 \leq M \leq 300\,000$。 - $1 \leq S_j \leq T_j \leq 1\,000\,000$（$1 \leq j \leq M$）。 - 所有输入值均为整数。 由 ChatGPT 5 翻译