http://acm.hdu.edu.cn/showproblem.php?pid=6602
终于能够看懂的题解:
https://blog.csdn.net/qq_40871466/article/details/97189033
依次枚举r,对r寻找可行的最小的l,查找成功则尝试更新。
假如每次把合法区间+1,把非法区间-1,那么对一段区间求区间和表示什么呢?
k=2
1 4 1 4 2 1 2
r=1,均为非法区间
-1 0 0 0 0 0 0
r=2,均为非法区间
-2 -1 0 0 0 0 0
r=3,对于r位置的元素1,[1,1]是合法区间,[2,3]是非法区间
-1 -2 -1 0 0 0 0
r=4,对于r位置的元素2,[1,2]是合法区间,[3,4]是非法区间
0 -1 -2 -1 0 0 0
此时出现了第一个>=0位置,更新答案[1,4]
r=5,均为非法区间
-1 -2 -3 -2 -1 0 0
r=6,对于r位置的元素1,[1,3]是合法区间,[4,6]是非法区间
0 -1 -2 -3 -2 -1 0
r=7,对于r位置的元素2,[1,5]是合法区间,[6,7]是非法区间
1 0 -1 -2 -1 -2 -1
出现了