[AdditionalFile5602.zip](file://AdditionalFile5602.zip?type=additional_file)

#5602. 「JOI 2026 Semifinal」宝石商

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Semifinal T2 「宝石商 / 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)$ 能到访的时间段内有店铺开门的时刻，顾客 $i$ 就会进店购买 $C_{i}$ 颗宝石。反之，顾客 $i$ 就不会进店，也不会购买宝石。假设 JOI 君的店里有充足的宝石，不会发生售罄的情况。

给定 JOI 君店铺的顾客信息和开店时间方案，请编写程序计算对于每个方案，总共能卖出多少颗宝石。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行包含三个用空格分隔的整数 $L_i, R_i, C_i$ $(1\leq i\leq N)$。

接下来一行包含一个整数 $M$。

接下来 $M$ 行，每行包含两个用空格分隔的整数 $S_j, T_j$ $(1\leq j\leq M)$。

输出格式

输出 $M$ 行。在第 $j$ $(1 \leq j \leq M)$ 行输出方案 $j$ 中总共能卖出的宝石数量。

样例 1

输入

3
3 4 10
5 8 20
6 10 30
3
4 6
1 2
6 8

输出

60
0
50

在方案 $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

输入

4
10 90 1
40 60 2
10 20 4
80 90 8
3
1 15
1 60
1 100

输出

5
7
15

在方案 $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

输入

10
55 882 861052753
104 734 331227764
492 694 240198464
481 506 377367203
131 185 327968773
124 129 970226535
92 125 133053911
356 442 758055457
21 759 730522637
259 481 948997757
9
50 287
510 735
158 431
113 768
328 894
783 881
163 692
42 862
43 752

输出

4303050130
2163001618
3957825141
5678671254
4247422035
861052753
4575390808
5678671254
5678671254

此样例满足子任务 $1, 5$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 300000$
• $1 \leq L_{i} < R_{i} \leq 1000000$ $(1 \leq i \leq N)$
• $1 \leq C_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
• $1 \leq M \leq 300000$
• $1 \leq S_{j} \leq T_{j} \leq 1000000$ $(1 \leq j \leq M)$
• 输入的所有值均为整数。

详细子任务附加限制及分值如下表所示。