分数: 466 分
问题陈述
高桥在一家大型图书馆担任图书管理员。这个图书馆有 N 书架排列成一排,编号 1, 2, \ldots, N 从左到右。
书架 i (1 \leq i \leq N) 包含 A_i 书籍。这些书目前正在修复中,书架上的所有书 i 将于当天完成修复 D_i。修复完成后,这些书籍就可供借阅。也就是书架上的书 i 从当天起即可借出 D_i 以后(包括当天 D_i)。当书架上的书 i 被借出,用户支付费用 V_i 图书馆每本书日元。
高桥正在考虑 Q 贷款计划。每个计划都是独立于其他计划的;一个计划中借出的书籍不会影响其他计划。
计划中 j (1 \leq j \leq Q),连续的书架间隔 [L_j, R_j] (1 \leq L_j \leq R_j \leq N)和日期 已指定 T_j 。在这个计划中,区间的书架之中 [L_j, R_j],白天恢复完成的 T_j (即书架 i 满意 D_i \leq T_j)将拥有所有 A_i 书籍借出。书架上未完成修复的图书将不予外借。
当所有 A_i 书架上的书 i 被借出,赚取的费用为 A_i \times V_i 日元。
对于每个计划,确定从贷款中赚取的总费用。即计划中赚取的总费用 j 是:
\sum_{\substack{L_j \leq i \leq R_j \\ D_i \leq T_j}} A_i \times V_i
约束
- 1 \leq N
- 1 \leq Q
- N + Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^4
- 1 \leq D_i \leq 10^5
- 1 \leq V_i \leq 10^4
- 1 \leq L_j \leq R_j \leq N
- 1 \leq T_j \leq 10^5
- 所有输入均为整数
- 对于每个计划,答案最多为 2 \times 10^{13}
输入
N Q A_1 D_1 V_1 A_2 D_2 V_2 \vdots A_N D_N V_N L_1 R_1 T_1 L_2 R_2 T_2 \vdots L_Q R_Q T_Q
- 第一行包含书架数量 N 及贷款计划数量 Q,用空格分隔。
- 如下 N 行, i-第行包含书籍数量 A_i 在书架上 i,恢复完成日 D_i,以及每本书的费用 V_i,以空格分隔。
- 如下 Q 行, j第行包含左端点 L_j,右端点 R_j和日期 T_j 计划 j,以空格分隔。
输出
输出 Q 行。上 j第行,输出计划中赚取的总费用 j 作为整数。
示例输入 1
5 4 2 1 100 3 3 50 1 2 200 5 5 10 4 3 25 1 3 2 2 5 3 1 5 5 4 4 4
示例输出 1
400 450 700 0
示例输入 2
3 5 1 10 5 2 20 7 3 30 11 1 3 9 1 1 10 2 3 25 3 3 30 1 3 100
示例输出 2
0 5 14 33 52
示例输入 3
10 8 5 4 120 2 1 300 7 6 80 1 3 1000 4 5 250 6 2 90 3 8 400 8 7 60 10 4 30 9 9 110 1 10 4 3 7 5 2 9 2 5 10 8 1 1 3 4 6 10 7 10 6 2 5 1
示例输出 3
3040 2540 1140 3520 0 2540 300 600
示例输入 4
30 20 10 15 100 25 3 40 7 22 500 100 1 20 13 18 70 6 9 1000 80 30 15 2 5 600 45 12 90 11 7 250 9 40 800 30 25 35 16 2 120 5 17 900 60 11 45 3 35 700 22 6 110 14 28 330 50 19 55 8 4 1000 19 23 75 4 14 650 70 8 25 12 31 400 33 10 60 1 100000 10000 90 13 30 18 21 200 27 16 85 40 24 95 1 30 10 1 30 100000 5 20 18 10 15 7 16 30 25 1 8 5 21 26 99999 26 26 100000 3 27 12 8 23 30 12 29 20 2 2 2 4 4 1 14 18 35 19 30 23 6 17 11 24 30 31 1 1 14 7 13 40 28 30 15
示例输出 4
29020 95820 34450 4670 33320 4200 12555 10000 34770 41735 33615 0 2000 16340 27100 16990 19175 0 19370 0
示例输入 5
1 1 10000 100000 10000 1 1 99999
示例输出 5
0