CF1847D Professor Higashikata

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 $ .

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.

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.