五条悟被封印了

时间限制：每个测试点 3 秒
内存限制：256 MB
输入：标准输入
输出：标准输出

题目描述

如你所知，五条悟被封印了。为了帮助他，虎杖悠仁决定尝试用「逕庭拳」打破狱门疆。
狱门疆可以表示为一个由 $n$ 个整数组成的数组 $a_1, \ldots, a_n$，其中 $a_i$ 表示第 $i$ 面墙的稳定度。

虎杖可以对第 $i$ 面墙施加力量 $x$，之后会发生以下事件之一：

如果 $a_i \le x$，则墙被摧毁，下一次攻击的力量减少 $a_i$；然后虎杖转向下一面墙，剩余力量为 $x - a_i$；
如果 $x < a_i$，则力量保持 $x$，墙被击裂到足以让虎杖也能用力量 $x$ 转向下一面墙。

虎杖还不确定他将如何突破这些墙，因此他有 $q$ 个查询，由数字 $l_i$, $r_i$, $d_i$ 给出。对于每个查询，他想知道：如果初始可以使用 $[0, d_i]$ 中任意整数力量，在依次通过所有墙 $a_{l_i}, \ldots, a_{r_i}$ 后，他能获得的最大最终力量是多少。

请帮助虎杖回答这些查询。

输入格式

第一行包含两个整数 $n$ 和 $q$ —— 数组长度和查询数量（$1 \le n, q \le 3 \cdot 10^5$）。
第二行包含 $n$ 个整数 $a_i$ —— 数组元素（$0 \le a_i \le 10^9$）。
接下来的 $q$ 行中，第 $i$ 行包含三个整数 $l_i$, $r_i$, $d_i$，表示第 $i$ 个查询的参数（$1 \le l_i \le r_i \le n$；$1 \le d_i \le 10^9$）。

输出格式

输出 $q$ 个整数 —— 每个查询的答案，每行一个。

子任务评分

只有通过了当前子任务及其所有必要子任务的全部测试，才能获得该子任务对应的分数。

子任务	分数	额外限制	必要子任务	检查信息
0	–	样例	无	完整
1	7	$n, q, d_i \le 10$	0	首次错误
2	8	$n, q, d_i \le 500$	0,1	首次错误
3	10	$n, q \le 10^3$	0–2	首次错误
4	15	$n, q \le 10^4$；所有 $d_i$ 相等	无	首次错误
5	10	$n, q \le 10^4$	0–4	首次错误
6	25	所有 $d_i$ 相等	4	首次错误
7	25	无	0–6	首次错误

样例

样例 1

输入

输出

2
1
3

样例 2

输入

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

输出

Wy Online Judge

WyOJ

#611. IOIP 20260215 robot-queries-ioi