#P18349. Add One 3
Add One 3
Add One 3
给定一个长度为 的整数序列 。一次操作选择一个位置 ,令 。
有 个询问,每个询问给出一个区间 。求至少进行多少次操作,才能使 成为整个序列中唯一的最大和连续子段。如果无法实现,输出 。
连续子段由一对下标 确定,其和为 。比较时还允许选择空子段,空子段的和为 。因此,最终的区间 必须满足:
- 区间和严格大于 ;
- 区间和严格大于其他所有非空区间的和。
各个询问相互独立,操作只是假设进行,不会改变后续询问所使用的原序列。
输入格式
第一行一个整数 ,表示测试用例数。
对于每个测试用例:
- 第一行两个整数 ;
- 第二行 个整数 ;
- 接下来 行,每行两个整数 ,表示一个询问。
数据范围:
- ;
- ;
- ;
- ;
- 一个输入文件中所有 的和不超过 ,所有 的和也不超过 ,两个限制分别成立。
输出格式
对于每个询问输出一行一个整数,表示最少操作次数;无解时输出 。
样例输入 1
2
6 6
-1 2 -2 0 1 -1
1 1
1 2
1 3
1 4
1 5
1 6
1 1
0
1 1
样例输出 1
-1
2
-1
-1
4
5
1