AT_past20_o 超過クエリ

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$，初始时 $A$ 的所有元素均为 $0$。在第 $i=1,2,\ldots,T$ 个时间点，序列 $A$ 上会进行如下操作： - 对 $A_{L_i},A_{L_i+1},\dots,A_{R_i}$ 的每个元素加上 $V_i$。 给定 $Q$ 个询问，按顺序处理。第 $i$ 个询问如下： - 给定整数 $l_i,r_i,x_i$，输出 $A_{l_i}+A_{l_i+1}+\dots+A_{r_i}$ 第一次达到或超过 $x_i$ 的时间。如果在第 $T$ 次操作后 $A_{l_i}+A_{l_i+1}+\dots+A_{r_i}$ 仍然小于 $x_i$，输出 `-1`。

输入按如下格式从标准输入给出： > $N\ T\ Q$ > $L_1\ R_1\ V_1$ > $L_2\ R_2\ V_2$ > $\vdots$ > $L_T\ R_T\ V_T$ > $l_1\ r_1\ x_1$ > $l_2\ r_2\ x_2$ > $\vdots$ > $l_Q\ r_Q\ x_Q$

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

### 输入样例说明 1 序列 $A$ 的变化过程如下： - 第 $1$ 次操作后：$(0,0,3,3,3,0)$。 - 第 $2$ 次操作后：$(2,2,5,5,3,0)$。 - 第 $3$ 次操作后：$(2,6,9,9,7,4)$。 各个查询的答案如下： - 查询 1：$A_2+A_3+A_4+A_5$ 在第 2 次操作后首次达到或超过 15。 - 查询 2：$A_4+A_5$ 在第 1 次操作后首次达到或超过 5。 - 查询 3：第 3 次操作后 $A_6$ 仍然小于 5，故输出 `-1`。 - 查询 4：$A_1+A_2+\dots+A_6$ 在第 3 次操作后首次达到或超过 30。 ### 数据范围 - $1\leq N\leq 10^5$ - $1\leq T,Q\leq 10^5$ - $1\leq L_i\leq R_i\leq N$ - $1\leq V_i\leq 10^5$ - $1\leq l_i\leq r_i\leq N$ - $1\leq x_i\leq 10^{15}$ - 所有输入均为整数。 由 ChatGPT 5 翻译