考虑一个20分的\(O(n^2)\)做法:枚举答案区间\([l,r]\),那么显然要把尽可能多的1填入\([l,r]\)。使用前缀和计算\([l,r]\)中\(0\)的个数,那么填入后的价值可以\(O(1)\)计算。
然后区间内非\(0\)的数的和也可以\(O(1)\)计算
考虑优化这个做法:设\(g_i\)表示以\(i\)为右端点时,最大的\(l\)使得区间\([l,r]\)中的\(0\)的个数\(\leq k\)。
随着\(i\)的增大,\(g_i\)显然递增,所以可以在均摊\(O(n)\)的时间内计算\(g\)
如果\(l\geq g_i\),则区间内的所有\(0\)填\(1\)最划算,设\(s1\)为把数组内所有\(0\)视为\(1\)后的前缀和数组,则区间\([l,r]\)的价值为\(s1_r-s1_{l-1}\)。
枚举\(r\),我们需要求出\([g_r-1,r-1]\)中的\(s1\)的最小值。由于\(g_i\)随着\(i\)的递增而递增,所以可以用单调队列维护最小值。
如果\(l \le g_i\),则区间的价值为先把区间的所有\(0\)视为\(-1\),然后把\(k\)个\(-1\)反转为\(1\)后的区间和。(反转后区间和加上\(k*2\))
设\(s2\)为把数组内所有\(0\)视为\(-1\)后的前缀和数组,则区间\([l,r]\)的价值为\(s2_r-s2_{l-1}+k*2\)。
枚举\(r\),我们需要求出\([0,g_r-2]\)中的\(s2\)的最小值。可以用前缀最小值维护。
总时间复杂度\(O(n)\)