Professor Higashikata
Contest: Codeforces Round 882 (Div. 2)
Difficulty rating: 1900
Tags: data structures, dsu, greedy, implementation, strings

Josuke is tired of his peaceful life in Morioh. Following in his nephew Jotaro's footsteps, he decides to study hard and become a professor of computer science. While looking up competitive programming problems online, he comes across the following one:

Let $$$s$$$ be a binary string of length $$$n$$$. An operation on $$$s$$$ is defined as choosing two distinct integers $$$i$$$ and $$$j$$$ ($$$1 \leq i < j \leq n$$$), and swapping the characters $$$s_i, s_j$$$.

Consider the $$$m$$$ strings $$$t_1, t_2, \ldots, t_m$$$, where $$$t_i$$$ is the substring $$$^\dagger$$$ of $$$s$$$ from $$$l_i$$$ to $$$r_i$$$. Define $$$t(s) = t_1+t_2+\ldots+t_m$$$ as the concatenation of the strings $$$t_i$$$ in that order.

There are $$$q$$$ updates to the string. In the $$$i$$$-th update $$$s_{x_i}$$$ gets flipped. That is if $$$s_{x_i}=1$$$, then $$$s_{x_i}$$$ becomes $$$0$$$ and vice versa. After each update, find the minimum number of operations one must perform on $$$s$$$ to make $$$t(s)$$$ lexicographically as large$$$^\ddagger$$$ as possible.

Note that no operation is actually performed. We are only interested in the number of operations.

Help Josuke in his dream by solving the problem for him.

——————————————————————

$$$\dagger$$$ A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

$$$\ddagger$$$ A string $$$a$$$ is lexicographically larger than a string $$$b$$$ of the same length if and only if the following holds:

- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a $$$1$$$, and the string $$$b$$$ has a $$$0$$$.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \leq n,m,q \leq 2 \cdot 10^5$$$).

The next line contains a binary string $$$s$$$ of length $$$n$$$, consisting only of digits $$$0$$$ and $$$1$$$.

The $$$i$$$-th line of the next $$$m$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$).

The $$$i$$$-th line of the next $$$q$$$ lines contains a single integer $$$x_i$$$ ($$$1 \leq x_i \leq n$$$).

Output format:
Print $$$q$$$ integers. The $$$i$$$-th integer is the minimum number of operations that need to be performed on $$$s$$$ to get the lexicographically largest possible string $$$t(s)$$$ in the $$$i$$$-th round.

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

Note:
In the first test case,

Originally, $$$t(s) = s(1,2) + s(1,2) = 0101$$$.

After the $$$1$$$-st query, $$$s$$$ becomes $$$11$$$ and consequently $$$t$$$ becomes $$$1111$$$. You don't need to perform any operation as $$$t(s)$$$ is already the lexicographically largest string possible.

After the $$$2$$$-nd query, $$$s$$$ becomes $$$01$$$ and consequently $$$t$$$ becomes $$$0101$$$. You need to perform $$$1$$$ operation by swapping $$$s_1$$$ and $$$s_2$$$. Consequently, $$$t(s)$$$ becomes $$$1010$$$ which is the lexicographically largest string you can achieve.

Example input:
2 2 4
01
1 2
1 2
1
1
2
2

Example output:
0
1
0
1

Example input:
8 6 10
10011010
5 6
2 3
6 8
5 7
5 8
6 8
3
5
6
2
5
2
5
8
4
1

Example output:
2
3
2
2
1
2
2
2
2
2

Editorial:
Lets assume you know string $$$t$$$. String $$$t$$$ is made by positions in $$$s$$$. Lets denote $$$f(i) = $$$ position in $$$s$$$ from which $$$t_i$$$ is made. For maximising $$$t$$$ you need to make the starting elements in $$$t$$$ as large as possible. Now, to make $$$t$$$ lexicographically as large as possible, we need to swap positions in $$$s$$$. We can swap positions greedily. We first try making $$$s_{f(1)} = 1$$$. Then we try making $$$s_{f(2)} = 1$$$ and so on.
Now, suppose for two indices $$$i$$$,$$$j$$$ ($$$1 \leq i < j \leq |t|$$$) such that $$$f(i) = f(j)$$$, we know that index $$$j$$$ is waste. $$$t$$$ is basically the preference of indices in $$$s$$$ which should be equal to $$$1$$$. If $$$s_{f(j)}$$$ is to be set $$$1$$$, then it would already be set $$$1$$$ because before setting $$$s_{f(j)}$$$ equal to $$$1$$$ we would have already set $$$s_{f(i)}$$$ equal to $$$1$$$ because $$$f(i)$$$ is equal to $$$f(j)$$$. Hence, for each index $$$i$$$ in $$$s$$$, we only add its first occurrence in $$$t$$$. This makes the size of $$$t$$$ bound by size of $$$s$$$. Now, this $$$t$$$ can be found using various pbds like set,dsu,segment tree,etc.
Now, before answering the queries, we find the answer for the current string $$$s$$$. We know that there are $$$x$$$ ones and $$$n-x$$$ zeros in $$$s$$$. So, for each $$$i$$$ ($$$1 \leq i \leq min(x,|t|)$$$), we make $$$s_{f(i)} = 1$$$. Hence, the number of swaps needed will become number of positions $$$i$$$ ($$$1\leq i \leq min(x,|t|)$$$) such that $$$s_i=0$$$.
Now, in each query, there is exactly one positions that is either getting flipped from $$$0$$$ to $$$1$$$ or from $$$1$$$ to $$$0$$$. That is, $$$x$$$ is either getting changed to $$$x+1$$$ or $$$x-1$$$. You already know the answer for $$$x$$$. Now, if $$$x$$$ is getting reduced, then you need to decrease the answer by one if $$$x <= |t|$$$ and $$$s_{f(x)}=0$$$. If $$$x$$$ is increasing by one, then you need to add one to the answer if $$$x < |t|$$$ and $$$s_{f(x+1)} = 0$$$.
Time complexity - $$$O(n \log n + q)$$$.