5958: 进阶2.5.4超级马里奥
内存限制：1024 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：40
解决：10
题目描述
马里奥是世界著名的水管工。他“魁梧”的身材和惊人的跳跃能力在我们的记忆中留下了印象。
现在可怜的公主又遇到了麻烦，马里奥需要拯救他的爱人。
我们把通往Boss库巴城堡的路看作是一条线（长度为$n$），在每一个整数点i上都有一块高度为$h_i$的砖块。
现在的问题是，如果马里奥能跳的最大高度是$H$，他能在区间$[L，R]$中打到多少块砖。
现在可怜的公主又遇到了麻烦，马里奥需要拯救他的爱人。
我们把通往Boss库巴城堡的路看作是一条线（长度为$n$），在每一个整数点i上都有一块高度为$h_i$的砖块。
现在的问题是，如果马里奥能跳的最大高度是$H$，他能在区间$[L，R]$中打到多少块砖。
输入
第一行跟着一个整数T，即测试数据的数量。
对于每个测试数据。
第一行包含两个整数n，m（1<=n<=$10^5$，1<=m<=$10^5$），n是道路的长度，m是查询的数量。
下一行包含n个整数，是每块砖的高度，范围是[0, $10^9$]。
接下来的m行，每行包含三个整数L，R，H。( 0 <= L <= R < n 0 <= H <= $10^9$。)
对于每个测试数据。
第一行包含两个整数n，m（1<=n<=$10^5$，1<=m<=$10^5$），n是道路的长度，m是查询的数量。
下一行包含n个整数，是每块砖的高度，范围是[0, $10^9$]。
接下来的m行，每行包含三个整数L，R，H。( 0 <= L <= R < n 0 <= H <= $10^9$。)
输出
对每个数据点 输出m+1行：
第1行为 Case x: (x代表当前数据点编号)
后m行为查询的答案,一行一个整数
第1行为 Case x: (x代表当前数据点编号)
后m行为查询的答案,一行一个整数
样例输入 复制
1
10 10
0 5 2 7 5 4 3 8 7 7
2 8 6
3 5 0
1 3 1
1 9 4
0 1 0
3 5 5
5 5 1
4 6 3
1 5 7
5 7 3样例输出 复制
Case 1:
4
0
0
3
1
2
0
1
5
1