P12664 [KOI 2023 Round 2] 烤肉派对

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

今天是烤肉派对的日子。为了配合派对的氛围，在一条很长的烤架上总共放了 $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$ 个人能够吃到的肉的美味值总和。

**限制条件** - 所有给定数值均为整数。 - $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 完成