Codeforces Round 882 (Div. 2) |
---|
Finished |
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:
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$$$).
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.
2 2 4 01 1 2 1 2 1 1 2 2
0 1 0 1
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
2 3 2 2 1 2 2 2 2 2
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.
Name |
---|