lg8945题解

考虑一个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)\)

巴特西

lg8945题解

最新文章

热门文章