Kirk and a Binary String (hard version)
Contest: Codeforces Round 581 (Div. 2)
Difficulty rating: 2100
Tags: data structures, greedy, math, strings

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 < i_2 < \ldots < 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.

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

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
110

Example output:
010

Example input:
010

Example output:
010

Editorial:
Solution 1: Let's call a string $$$p$$$ fixed if there isn't another string $$$t$$$ of the same length which satisfies the first condition of the statement (it was about the same lengths of the longest nondecreasing subsequences on substrings). The following statements are obivous:
• string $$$10$$$ is fixed;
• if strings $$$p$$$ and $$$q$$$ are fixed, then their concatenation $$$pq$$$ is fixed;
• if a string $$$p$$$ is fixed, then the string $$$1p0$$$ is fixed;
• each fixed string contains the same number of ones and zeroes;
• the length of the longest nondecreasing subsequence for any fixed string is equal to the half of its length, which can be obtained by taking all zeroes or all ones;
So if we erase all fixed strings from the given string, the remaining parts consists of zeroes at prefix and ones at suffix; it is obvious that we can change all these ones to zeroes and the string still satisfies the condition.
Solution 2: If we change any $$$1$$$ to $$$0$$$ and the longest nondecreasing sequence of the whole string remains the same, then we are able to change it to $$$0$$$. To count the longest nondecreasing sequence of a new string, store and maintain following arrays: $$$dp^p_i$$$ — the longest nondecreasing sequence of the substring $$$s_{1 \ldots i}$$$; $$$zero_i$$$ — number of zeroes in the substring $$$s_{1 \ldots i}$$$; $$$dp^s_i$$$ — the longest nondecreasing sequence of the substring $$$s_{i \ldots n}$$$ and $$$ones_i$$$ — number of ones in the substring $$$s_{i \ldots n}$$$; now, if we change $$$1$$$ to $$$0$$$ at a position $$$i$$$, then the length of the longest nondecreasing sequence of a new string is $$$\max(dp^p_{i-1}+ones_{i+1},zero_{i-1}+1+dp^s_{i+1})$$$.