CHDOJ
首页
题库
题单
比赛
评测
用户
讨论
帮助
工具
云剪贴板
树图画板
代码对比
登录
注册
3044: 爱读书的zgt
时间限制:2000 ms
内存限制:128 MB
上传者:
提交:3
通过:3
提交
提交记录
讨论
统计
题目描述
$wx$和$zgt$应$hyd$的邀请,来到$hyd$家做客。$hyd$家里面有一间超级大的书房,书房里面一共有$n$个书柜,第$i$个书柜有$a_{i}$本书。喜欢读书的$zgt$非常高兴,但是$wx$和$hyd$早已经商量好了,只要$zgt$可以解决$wx$和$hyd$提出的难题,$zgt$就可以在$hyd$的书房里为所欲为。
$wx$给出了一个函数$f(l,r) = max(ai\ |\ l<=i<=r)$,代表第$l$个书柜到第$r$个书柜中,拥有书最多的书柜有多少本书。然后对$zgt$进行$q$次询问,每次都给出单独的$l_{j}$和$r_{j}$,要求$zgt$ 给出对应的$f(l_{j},r_{j})$的值。
$zgt$很快的就解决掉了这个问题,于是$hyd$加深了难度:$hyd$也给出了一个函数$g(x,l,r) = \sum_{y=l}^{r}f(x,y)$,也对$zgt$进行$q$次询问,即每次给出单独的$x_{j},l_{j}$ 和$r_{j}$,求$g(x_{j},l_{j},r_{j})$的值。
$zgt$这次陷入了困境,想要求助于你,请你帮$zgt$解决这个问题。
输入格式
输入第一行为一个整数$T(T \leq 30)$,表示一共有$T$组测试数据。
对于每组测试数据:
第一行有两个整数$n(1 \leq n \leq 10^5)$,$q(1 \leq m \leq 10^5)$,分别表示书柜的数量和询问数。
第二行有$n$个整数,其中第$i$个整数$a_{i}(1 \leq a_{i} \leq 10^9)$,表示第$i$个书柜中书的数量。
接下来$q$行,每行有三个整数$x_{j}(1 \leq x_{j} \leq l_{j})$,$l_{j}(x_{j} \leq l_{j} \leq r_{j})$,$r_{j}(l_{j} \leq r_{j} \leq n)$,定义如题意。
输出格式
对于每组测试数据一行输出$q$个整数,第$j$个数表示第$j$次询问的答案。
输入样例
复制
2 6 3 2 3 6 5 2 9 1 2 4 5 5 6 3 4 7 6 3 6 5 4 3 2 1 2 3 3 5 6 6 1 4 5
输出样例
复制
15 11 21 5 2 12
数据范围与提示
分类标签
2018年长安大学第五届程序设计竞赛新生赛