首页 > 试题广场 >

移山

[编程题]移山
  • 热度指数：1171 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
天帝被愚公的诚心感动，命令手下的仙人帮助移山。
然而仙人的法术也是有局限性的，山势连绵起伏，法术并不能直接把山移走。每次施法，可以把一段连续区域的山头移走相同高度。现在愚公想知道什么时候会有至少一个山头高度小于等于0
给出一个长度为 n 的数组 a_1,a_2,...,a_n ，和 m 表示山头的高度和可以施法的次数，每次施法还会给出左右端点 L,R 和高度 h，表示将 a_L,...a_R 依次减去 h。问在哪次操作之后存在一个 a_i \leq 0？（数据保证这样的时刻存在。）

输入描述:
第一行两个数 n 和 m，表示山头数量和施法次数。
第二行n个数，分别表示a_1,a_2,...,a_n ，即第一个山头到第n 个山头的高度。
接下来m行，每行三个数L,R,h，表示一次施法的具体参数。

1 \leq n,m \leq 10^5, 1 \leq h, a_i \leq 10^9, 1 \leq L\leq R \leq n，均为整数


输出描述:
输出一个整数，表示答案。数据保证答案存在。
示例1

输入

5 4
6 5 3 4 6
1 3 2
4 4 2
3 5 1
1 5 6

输出

3

说明

第一次操作之后山头变成4 3 1 4 6
第二次操作之后山头变成4 3 1 2 6
第三次操作之后山头变成4 3 0 1 5
其中第三个山头高度小于等于了0，可见，在第三次施法之后有一个山头的高度变成了0
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

线段树 小米集团
难度：
0条回答 348浏览

热门推荐

相关试题

移山

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号