待补 http://acm.hdu.edu.cn/showproblem.php?pid=6602

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

出现了

原文地址:https://www.cnblogs.com/Yinku/p/11253573.html