#P18336. Sumotonic Sequences
Sumotonic Sequences
Sumotonic Sequences
一个整数序列称为单调的,当且仅当它是非递减序列或者非递增序列。
一个序列称为 sumotonic,当且仅当它能表示为任意多个只含非负值的单调序列的逐项和。这些单调序列与原序列长度相同,每个序列可以选择自己的单调方向。
给定序列 和 次操作。每次操作向 的一个连续区间加上等差数列:对于给定的 ,将
分别改为
判断初始序列以及每次操作后的序列是否为 sumotonic。操作会永久生效,后续操作在之前的修改结果上继续进行。
输入格式
第一行包含测试用例数 。
每组测试用例的第一行包含两个整数 ,分别表示序列长度和操作次数。
第二行包含序列的初始值 。
接下来 行,每行包含四个整数 ,表示向区间 加上首项为 、公差为 的等差数列。
输出格式
对每组测试用例输出 行。
第一行表示初始序列的答案;此后第 行表示第 次操作后的答案。
如果相应序列是 sumotonic,则输出 YES,否则输出 NO。
数据范围
- ;
- ;
- ;
- 初始 ;
- 每次操作 ;
- 每次操作 ;
- 所有测试用例的 之和不超过 。
始终为正数。 的上界限制的是初始值,操作后的数值可以超过 。当 时,只给一个元素加上 ,公差 不影响这一操作的结果。
样例输入 1
1
5 2
5 8 5 2 4
5 5 6 6
2 4 1 3
样例输出 1
NO
NO
YES