T126268 「SWTR-05」Subsequence

小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。$q$ 次询问，每次询问给定 $l,r,v$，求： $$\sum_{l\leq i\leq j\leq r}\operatorname{sum}(i,j)[\operatorname{max}(i,j)\leq v]$$ - $\operatorname{sum}(i,j)$ 表示区间 $[i,j]$ 的和，$\operatorname{max}(i,j)$ 表示区间 $[i,j]$ 的最大值。 - 答案可能较大，请输出答案对 $2^{32}$ 取模的结果。

第一行两个整数 $n,m$。 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示这个序列。 接下来 $m$ 行每行三个整数 $l,r,v$ 表示一个询问。

输出 $m$ 行表示答案。

「样例说明」 样例 $1$ 第一组询问：区间 $[1,4]$ 共有 $4$ 个子区间最大值不超过 $7$，分别是 $[1,1],[3,3],[3,4],[4,4]$，所有元素的和为 $1+7+10+3=21$。 「数据范围与约定」 **本题采用捆绑测试**。 - Subtask 1（5 points）：$n,m\leq 100$。 - Subtask 2（8 points）：$n,m\leq 500$。 - Subtask 3（12 points）：$n,m\leq 2\times 10^3$。 - Subtask 4（17 points）：$n,m\leq 4\times 10^4$。 - Subtask 5（18 points）：所有 $v$ 相等。 - Subtask 6（15 points）：$\max a_i - \min a_i\leq 20$。 - Subtask 7（25 points）：无特殊限制。 对于 $100\%$ 的数据：$1 \leq n,m \leq 2\times 10^5$，$1 \leq a_i,v \leq 10^9$，$1\leq l\leq r\leq n$。 前 $4$ 个 Subtask 时限 $2\rm{s}$。第 $5\sim 7$ 个 Subtask 时限 $4\rm{s}$。 --- 「题目来源」 [Sweet Round 05](https://www.luogu.com.cn/contest/28195) F。 idea：[ET2006](https://www.luogu.com.cn/user/115194)，solution：[chenxia25](https://www.luogu.com.cn/user/138400) & [Alex_Wei](https://www.luogu.com.cn/user/123294)。