A15981. 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$ .
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$ ).
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.
输入输出样例
输入 #1
2 2 4 01 1 2 1 2 1 1 2 2
输出 #1
0 1 0 1
输入 #2
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
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.
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.