P3428.第3题-和Tk的游戏
题目内容
Tk 有一个长度为 n 的数组 a1,a2,…,an
，其中每个元素 ai等于 −1 或 1 。
你需要与 Tk 进行 m 轮游戏，每轮游戏相互独立，（即数组的改变并不会影响其他轮次）；
S=∑i=lrai
随后将区间[l,r] 从数组中删除，剩余元素按原顺序拼接；你的任务是，在新的数组中找到一个区间 [l1,r1] 满足
区间长度与被删除的区间相同，即 r1−l1=r−l 。
且 ∑i=l1r1ai>S；
如果存在多个满足条件的区间， 可以输出任意一个；如果不存在，则输出 −1 。
输入描述
每个测试文件均包含多组测试数据:
除此之外，保证单个测试文件的∑n、∑m 及所有被删除区间长度 之和均不超过 105 ;
接下来对于每组测试数据:
第一行输入两个整数 n 和 m(1≤n,m≤105)， 分别表示数组长度和游戏轮次；
第二行输入 n 个数组 a1,a2,…,an(ai∈{−1,1})，表示初始的数组。
此后 m 行，每行输入两个整数 l 和 r(1≤l≤r≤n) ,表示 Tk 选择的删除区间。
输出描述
对于每组测试数据，输出 m 行，每行对应一轮游戏的答案。
如果无解，输出 −1 。
否则，输出两个整数 l1 和 r1(1≤l1≤r1≤n−(r−l+1)) 表示你选取的区间。
样例1
输入
1
5 2
-1 1 1 -1 1
3 4
1 3
输出
2 3
-1
说明
第一轮游戏 S=0 ,删除后数组变为{−1,1,1}区间 [2,3] 满足答案。
第二轮游戏删除后数组变为{−1,1}长度小于 3 一定无解。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
