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 翻译