题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

今天是烤肉派对的日子。为了配合派对的氛围，在一条很长的烤架上总共放了 $N$ 块烤得很香的肉。

将这条烤架视为一条长度为 $10^9$ 的线段，左端为坐标 $0$，右端为坐标 $10^9$。每块肉都占据烤架上的某个区间，并且拥有一个用正整数表示的“美味值”。第 $i$ 块肉（$1 \leq i \leq N$）占据区间 $[s_i, e_i]$，其美味值为 $t_i$。多块肉可能重叠放置。

派对共有 $M$ 个人参加。每个人按照编号从 $1$ 到 $M$ 依次站到烤架前，各自领取要吃的烤肉。领取方法如下：

• 第 $j$ 个人（$1 \leq j \leq M$）带来了两根长签子，并分别插入坐标 $a_j + 0.1$ 和 $b_j + 0.9$ 的位置（其中 $a_j \leq b_j$）。插入坐标 $x$ 的签子会贯穿所有满足 $s_i \leq x \leq e_i$ 的第 $i$ 块肉。
• 然后，他会整根地拔起签子带回座位。此时，只要有一块肉被两根签子都贯穿，就可以被带走并从烤架上移除。
• 如果只有一根签子贯穿了一块肉，那么这块肉在途中会掉到地上，无法带回座位吃。
• 也就是说，只有同时被两根签子贯穿的肉才能顺利被带走并吃掉。

你是这场派对的主办者，对每个人究竟带走了哪些肉感到好奇。请计算出每个人最终能够吃掉的肉的美味值总和（注意不包括在途中掉落的肉）。

输入格式

第一行输入两个整数 $N$ 和 $M$，分别表示烤肉的数量和参加派对的人的数量。
接下来 $N$ 行中，第 $i$ 行包含三个整数 $s_i, e_i, t_i$，表示第 $i$ 块肉所占据的区间和其美味值。
接下来 $M$ 行中，第 $j$ 行包含两个整数 $a_j, b_j$，表示第 $j$ 个人插入签子的两个坐标。

输出格式

输出 $M$ 行，其中第 $j$ 行输出第 $j$ 个人能够吃到的肉的美味值总和。

5 3
2 7 3
5 6 9
3 5 2
1 3 6
4 8 7
3 6
2 4
5 5

3
0
9

6 3
1 12 1
2 11 10
3 10 100
4 9 1000
5 8 10000
6 7 100000
1 11
5 9
6 8

1
110
0

5 2
1 5 5
2 6 2
4 8 3
5 9 4
7 11 6
4 5
8 10

5
6

提示

限制条件

• 所有给定数值均为整数。
• $1 \leq N, M \leq 250\,000$
• $0 \leq s_i < e_i \leq 10^9 \quad (1 \leq i \leq N)$
• $1 \leq t_i \leq 10^9 \quad (1 \leq i \leq N)$
• $0 \leq a_j \leq b_j \leq 10^9 - 1 \quad (1 \leq j \leq M)$

子任务

1. （5 分）$N, M \leq 1\,000$
2. （9 分）$e_i - s_i \leq 5 \quad (1 \leq i \leq N)$
3. （11 分）$s_i < s_{i+1},\ e_i > e_{i+1} \quad (1 \leq i \leq N - 1)$
4. （23 分）$e_i - s_i = e_1 - s_1 \quad (2 \leq i \leq N)$
5. （52 分）无额外限制

翻译由 ChatGPT-4o 完成