题目描述

题目译自 XXXI Olimpiada Informatyczna – II etap Ciąg binarny

Bajtocy 是二进制序列的狂热爱好者。对于给定的二进制序列 $a_1, a_2, \ldots, a_s$ 和非负整数 $k$，其 $k$-近似序列定义为任意二进制序列 $b_1, b_2, \ldots, b_s$，满足以下条件：

1. $0 \leq b_i \leq a_i \leq 1$ 对于 $1 \leq i \leq s$；
2. 位置 $1 \leq i \leq s-1$ 处 $b_i \neq b_{i+1}$ 的数量不超过 $k$；
3. 序列和 $b_1 + b_2 + \ldots + b_s$ 尽可能大。

Bajtocy 拥有一个心爱的二进制序列 $x_1, x_2, \ldots, x_S$。由于序列可能极长，采用压缩形式输入：由 $n$ 个正整数 $d_1, d_2, \ldots, d_n$ 表示，序列从 $d_1$ 个 $1$ 开始，接着 $d_2$ 个 $0$，$d_3$ 个 $1$，依此类推，形式为 $1^{d_1} 0^{d_2} 1^{d_3} \ldots$。

你的任务是帮助 Bajtocy 计算其心爱序列某些连续片段的 $k$-近似序列和。具体为，回答 $q$ 次查询，每查询包含整数 $k$ 和两个整数 $l, r$，需计算序列 $x_l, x_{l+1}, \ldots, x_r$ 的 $k$-近似序列和。

输入格式

第一行包含两个整数 $n, q$ $(1 \leq n, q \leq 1000000)$，分别表示序列压缩描述的长度和查询次数。

第二行包含 $n$ 个正整数 $d_1, d_2, \ldots, d_n$ $(1 \leq S \leq 10^9, S = d_1 + d_2 + \ldots + d_n)$，表示序列中各块的长度。

接下来的 $q$ 行，每行包含三个整数 $l_i, r_i, k_i$ $(1 \leq l_i \leq r_i \leq S, 0 \leq k_i \leq 10^9)$，表示查询序列 $x_{l_i}, x_{l_i+1}, \ldots, x_{r_i}$ 的 $k_i$-近似序列和。

输出格式

输出 $q$ 行，第 $i$ 行包含一个整数，表示序列 $x_{l_i}, x_{l_i+1}, \ldots, x_{r_i}$ 的 $k_i$-近似序列和。

5 5
1 1 2 1 2
1 4 2
1 4 3
2 6 0
1 7 2
3 7 1

3
3
0
3
2

Bajtocy 的心爱序列为 $1, 0, 1, 1, 0, 1, 1$，共 $5$ 次查询：

1. 查询 $1$：$2$-近似序列，片段 $1, 0, 1, 1$，其本身为 $2$-近似序列，和为 $3$。
2. 查询 $2$：$3$-近似序列，同一片段 $1, 0, 1, 1$，亦为其 $3$-近似序列，和为 $3$。
3. 查询 $3$：$0$-近似序列，片段 $0, 1, 1, 0, 1$，$0$-近似为常序列 $0, 0, 0, 0, 0$，和为 $0$。
4. 查询 $4$：$2$-近似序列，整个序列 $1, 0, 1, 1, 0, 1, 1$，$2$-近似为 $1, 0, 0, 0, 0, 1, 1$，和为 $3$。
5. 查询 $5$：$1$-近似序列，片段 $1, 1, 0, 1, 1$，可能 $1$-近似为 $1, 1, 0, 0, 0$ 或 $0, 0, 0, 1, 1$，均和为 $2$。

附加样例

1. $n=3, S=9, q=450$，查询覆盖每个区间和 $k$ 从 $0$ 到 $9$。
2. $n=5, S=500, q=500$，$l_i = 1, r_i = i, k_i = 2$ 对于 $1 \leq i \leq q$，块长度为 $2, 1, 1, 1, 495$，答案依次为 $1, 2, 2, 3, 2, 3, 4, 5, 6, 7, 8, \ldots$。
3. $n=500, q=500$，$l_i = i, r_i = i+9, k_i = 3$ 对于 $1 \leq i \leq q$，块长度为 $3, 2, 3, 2, \ldots$，答案依次为 $6, 5, 5, 6, 3, 6, 5, 5, 6, 3, \ldots$。
4. $n=10^4, S=10^9, q=10^4$，$l_i = 1, r_i = 10^9, k_i = 10^9$ 对于 $1 \leq i \leq q$，答案为 $987654321$。
5. $n=10^6, q=10^6$，$r_i - l_i \leq 10$ 对于 $1 \leq i \leq q$。

数据范围与提示

详细子任务附加限制及分值如下表所示。