CF1876G Clubstep

有一个极其困难的视频游戏，是 Chaneka 最喜欢的游戏之一。其中最难的关卡之一叫做 Clubstep。Clubstep 由 $n$ 个部分组成，编号从 $1$ 到 $n$。Chaneka 已经练习了很久，因此她对每个部分 $i$ 的熟练度为 $a_i$。 之后，Chaneka 可以多次（也可以不进行）尝试 Clubstep。在每次尝试中，她会在某一个部分死亡。如果一次尝试在第 $p$ 个部分死亡，意味着她只成功通过了所有 $1 \leq k \leq p-1$ 的部分，并且没有到达所有 $p+1 \leq k \leq n$ 的部分。一次在第 $p$ 部分死亡的尝试需要 $p$ 秒。 已知 Chaneka 在她死亡的部分提升得比其他部分多得多。同时，在一次尝试中，她对没有到达的部分几乎没有练习。因此，一次在第 $p$ 部分死亡的尝试对熟练度的影响如下： - Chaneka 在第 $p$ 部分的熟练度增加 $2$。 - 对于所有 $1 \leq k \leq p-1$ 的部分，熟练度各增加 $1$。 接下来有 $q$ 个询问。对于第 $j$ 个询问，给定三个整数 $l_j$、$r_j$ 和 $x_j$。你需要求出 Chaneka 至少需要多少时间（以秒为单位），才能使得每个 $p$ 满足 $l_j \leq p \leq r_j$ 时，其熟练度至少为 $x_j$。注意每个询问是独立的，某个询问中的尝试不会影响其他询问中的熟练度。

第一行包含一个整数 $n$（$1 \leq n \leq 3\cdot10^5$），表示 Clubstep 的部分数量。 第二行包含 $n$ 个整数 $a_1,a_2,a_3,\ldots,a_n$（$1\leq a_i\leq10^9$），表示 Chaneka 对每个部分的熟练度。 第三行包含一个整数 $q$（$1\leq q\leq3\cdot10^5$），表示询问的数量。 接下来 $q$ 行，每行包含三个整数 $l_j$、$r_j$ 和 $x_j$（$1\leq l_j\leq r_j\leq n$；$1\leq x_j\leq10^9$），描述第 $j$ 个询问。

输出 $q$ 行，每行一个整数。第 $j$ 行的整数表示 Chaneka 至少需要多少秒，才能使得每个 $l_j \leq p \leq r_j$ 的部分熟练度至少为 $x_j$。

对于第 $1$ 个询问，一种可行的策略如下： 1. 进行 $1$ 次在第 $1$ 部分死亡的尝试。耗时 $1$ 秒。熟练度变为 $[3, 3, 2, 1, 2]$。 2. 进行 $1$ 次在第 $4$ 部分死亡的尝试。耗时 $4$ 秒。熟练度变为 $[4, 4, 3, 3, 2]$。 3. 进行 $2$ 次在第 $5$ 部分死亡的尝试。耗时 $10$ 秒。熟练度变为 $[6, 6, 5, 5, 6]$。 总耗时为 $1+4+10=15$ 秒。 对于第 $2$ 个询问，一种可行的策略如下： 1. 进行 $1$ 次在第 $3$ 部分死亡的尝试。耗时 $3$ 秒。熟练度变为 $[2, 4, 4, 1, 2]$。 2. 进行 $2$ 次在第 $4$ 部分死亡的尝试。耗时 $8$ 秒。熟练度变为 $[4, 6, 6, 5, 2]$。 总耗时为 $3+8=11$ 秒。 由 ChatGPT 4.1 翻译