P11622 [Ynoi Easy Round 2025] TEST_176

你有一个长度为 $n$ 的序列，其中第 $i$ 个元素的值为 $a_i$。 现在有 $q$ 组询问，每组询问给定 $x,l,r$，表示你刚开始有一个数字 $x$ ，然后你从序列的第 $l$ 个位置走到第 $r$ 个位置，每经过一个位置就执行 $x=\max(x,a_i-x)$。你需要回答每组询问最后 $x$ 的值。

第一行两个整数 $n$ 和 $q$，分别表示序列长以及询问数量。 第二行包含 $n$ 个整数，其中第 $i$ 个整数表示序列第 $i$ 个元素的值 $a_i$。 接下来 $q$ 行，每行三个整数 $x,l,r$，含义如题目描述中所示。

输出 $q$ 行，每行一个整数，其中第 $i$ 行的整数表示第 $i$ 组询问的答案。

### 样例解释 对于第一组询问，$x$ 的值为 $2(初始)→2→2→4→4→6→6→6→6→7→7(最终)$。 Idea：zx2003，Solution：zx2003，Code：zx2003，Data：zx2003 ### 限制与约定 对于所有数据，保证 $ 1\leq n,q\leq 2\times 10^5,1\leq l \leq r \leq n，0\leq |x|,|a_i|\leq 10^{13}$。 | 子任务编号 | $n,q\leq$ | 特殊性质 | 子任务分值 | | :--------: | :-----------: | :---------------------------: | :--------: | | $1$ | $1000$ | 无 | $8$ | | $2$ | $80000$ | $-500\leq x,a_i\leq 500$ | $16$ | | $3$ | $2\times10^5$ | $10^6\leq x,a_i\leq 10^6$ 且 $l=1$ | $25$ | | $4$ | $2\times10^5$ | $l=1$ | $24$ | | $5$ | $2\times10^5$ | 无 | $27$ |