「Codeforces 1204D2」Kirk and a Binary String (hard version)

给定一个长度为 \(n\) 的 \(01\) 字符串 \(s\)，求一个长度为 \(n\) 的 \(01\) 字符串 \(t\)，满足 \(\forall 1\le l\le r\le n:f(s[l,r])=f(t[l,r])\)，其中 \(f(s[l,r])\) 表示 \(s\) 中第 \(l\) 个字符到第 \(r\) 个字符组成的子串的最长不下降子序列的长度，\(f(t[l,r])\) 同理。

在满足以上条件的同时，你需要最大化 \(t\) 中 \(0\) 的数量。

\(n\le 10^5\)

显然一定是把 \(s\) 中的若干个 \(1\) 改成 \(0\)，且每段连续的 \(1\) 一定是修改它的一个前缀。

我们发现，一个区间的最长不下降子序列一定可以表示成在区间的某个位置断开（特殊地，也可以在左端点的前面或右端点的后面），然后选断点左边的 \(0\) 和断点右边的 \(1\)，显然这个断点需要满足左边 \(0\) 的个数加上右边 \(1\) 的个数等于这个区间的最长不下降子序列长度。我们称这样的断点为这个区间的答案断点。显然答案断点必须满足右边 \(1\) 的个数大于等于 \(0\) 的个数，左边 \(0\) 的个数大于等于 \(1\) 的个数。但这个不是充要条件。

考虑一个 \(1\) 能变成 \(0\) 的条件，假设这个位置为 \(i\)，那就是所有 \(i+1\) 开始的所有区间必须存在一个最长不下降子序列是全为 \(1\) 的。

我们又发现，只要 \([i+1,n]\) 这个区间满足条件，所有区间就一定满足条件。

先给出做法：从后往前扫，记 \(cnt_i\) 表示 \(i\sim n\) 没有改变的位置中 \(0\) 的个数减去 \(1\) 的个数的值，那么 \(cnt_{i+1}=0\) 时把 \(i\) 这个位置改成 \(0\)。

考虑这样为什么是对的（以下内容纯属口胡）。对于 \([i+1,n]\) 的某个点 \(j\)，我们把 \(j\sim n\) 的所有位置中 \(0\) 的个数减去 \(1\) 的个数的值记为 \(sum_j\)。由于改变只会是 \(1\) 变成 \(0\)，所以有 \(cnt_j\le sum_j\)。又因为只要碰到 \(1\) 且 \(cnt_j=0\) 就会改变，所以 \(sum_j\ge cnt_j\ge 0\)。要 \(j\) 前面的位置要成为答案断点，必须有 \(sum_j\le 0\)，所以 \(sum_j\) 只能等于 \(0\)，即 \(0\) 的个数等于 \(1\) 的个数。因为 \(j\sim n\) 满足这个条件，当前的 \(cnt_{i+1}=0\)，所以 \(i+1\sim j-1\) 所有位置中 \(0\) 的个数一定小于等于 \(1\) 的个数，要符合答案断点的必要条件，又只能是取等于。于是我们可以把 \(i+1\sim j-1\) 的决策替换成 \(1\)，于是 \(i+1\sim n\) 就一定存在一个全为 \(1\) 的最长不下降子序列。

差不多口胡完了，直接做就可以了。