CF1204D2.Kirk and a Binary String (hard version)

The only difference between easy and hard versions is the length of the string. You can hack this problem if you solve it. But you can hack the previous problem only if you solve both problems.

Kirk has a binary string $s$ (a string which consists of zeroes and ones) of length $n$ and he is asking you to find a binary string $t$ of the same length which satisfies the following conditions:

• For any $l$ and $r$ ($1 \leq l \leq r \leq n$) the length of the longest non-decreasing subsequence of the substring $s_{l}s_{l+1} \ldots s_{r}$ is equal to the length of the longest non-decreasing subsequence of the substring $t_{l}t_{l+1} \ldots t_{r}$;
• The number of zeroes in $t$ is the maximum possible.

A non-decreasing subsequence of a string $p$ is a sequence of indices $i_1, i_2, \ldots, i_k$ such that $i_1 \lt i_2 \lt \ldots \lt i_k$ and $p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k}$. The length of the subsequence is $k$.

If there are multiple substrings which satisfy the conditions, output any.

简单版本与困难版本的唯一区别在于字符串的长度。如果你解决了本题，就可以对本题进行 Hack；但只有当你同时解决了本题和上一题时，才可以对上一题进行 Hack。

Kirk 有一个长度为 $n$ 的二进制字符串 $s$（即仅由 0 和 1 组成的字符串），他请你找出一个同样长度的二进制字符串 $t$，使其满足以下条件：

• 对任意 $l$ 和 $r$（$1 \leq l \leq r \leq n$），子串 $s_{l}s_{l+1} \ldots s_{r}$ 的最长非递减子序列的长度，等于子串 $t_{l}t_{l+1} \ldots t_{r}$ 的最长非递减子序列的长度；
• $t$ 中 0 的个数尽可能多。

字符串 $p$ 的一个非递减子序列是指一组下标 $i_1, i_2, \ldots, i_k$，满足 $i_1 \lt i_2 \lt \ldots \lt i_k$ 且 $p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k}$。该子序列的长度为 $k$。

若存在多个满足条件的字符串 $t$，输出任意一个即可。

The first line contains a binary string of length not more than $10^5$.

第一行包含一个长度不超过 $10^5$ 的二进制字符串。

Output a binary string which satisfied the above conditions. If there are many such strings, output any of them.

输出一个满足上述条件的二进制字符串。如果存在多个这样的字符串，则输出其中任意一个即可。

In the first example:

• For the substrings of the length $1$ the length of the longest non-decreasing subsequnce is $1$;
• For $l = 1, r = 2$ the longest non-decreasing subsequnce of the substring $s_{1}s_{2}$ is $11$ and the longest non-decreasing subsequnce of the substring $t_{1}t_{2}$ is $01$;
• For $l = 1, r = 3$ the longest non-decreasing subsequnce of the substring $s_{1}s_{3}$ is $11$ and the longest non-decreasing subsequnce of the substring $t_{1}t_{3}$ is $00$;
• For $l = 2, r = 3$ the longest non-decreasing subsequnce of the substring $s_{2}s_{3}$ is $1$ and the longest non-decreasing subsequnce of the substring $t_{2}t_{3}$ is $1$;

The second example is similar to the first one.

在第一个例子中：

• 对于长度为 $1$ 的子串，最长非递减子序列的长度为 $1$；
• 当 $l = 1, r = 2$ 时，子串 $s_{1}s_{2}$ 的最长非递减子序列为 $11$，子串 $t_{1}t_{2}$ 的最长非递减子序列为 $01$；
• 当 $l = 1, r = 3$ 时，子串 $s_{1}s_{3}$ 的最长非递减子序列为 $11$，子串 $t_{1}t_{3}$ 的最长非递减子序列为 $00$；
• 当 $l = 2, r = 3$ 时，子串 $s_{2}s_{3}$ 的最长非递减子序列为 $1$，子串 $t_{2}t_{3}$ 的最长非递减子序列为 $1$；

第二个例子与第一个例子类似。