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

乔鲁克厌倦了在杜王町的平静生活。他追随侄子东方仗助的脚步，决定努力学习，成为一名计算机科学教授。在上网查阅竞赛编程题目时，他遇到了下面这道题：

设 $s$ 是一个长度为 $n$ 的二进制字符串。对 $s$ 执行一次操作定义为：选择两个不同的整数 $i$ 和 $j$（满足 $1 \leq i < j \leq n$），并交换字符 $s_i$ 与 $s_j$。

考虑 $m$ 个字符串 $t_1, t_2, \ldots, t_m$，其中 $t_i$ 是 $s$ 在区间 $[l_i, r_i]$ 上的子串$^\dagger$。定义 $t(s) = t_1 + t_2 + \ldots + t_m$ 为这些字符串 $t_i$ 按此顺序拼接而成的字符串。

共有 $q$ 次对字符串 $s$ 的更新操作。在第 $i$ 次更新中，$s_{x_i}$ 被翻转（即若 $s_{x_i}=1$，则变为 $0$；若为 $0$，则变为 $1$）。每次更新后，请计算：为使 $t(s)$ 的字典序$^\ddagger$尽可能大，需对 $s$ 执行的最少操作次数。

注意：实际上并不真正执行任何操作，我们只关心所需操作的最少次数。

请帮助乔鲁克实现他的梦想，解决该问题。

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

$\dagger$ 若字符串 $a$ 可通过从字符串 $b$ 的开头删除若干（可能为零或全部）字符、并从结尾删除若干（可能为零或全部）字符而得到，则称 $a$ 是 $b$ 的子串。

$\ddagger$ 对于两个等长字符串 $a$ 和 $b$，当且仅当满足以下条件时，称 $a$ 的字典序大于 $b$：

• 在 $a$ 与 $b$ 首次出现差异的位置上，$a$ 对应字符为 $1$，而 $b$ 对应字符为 $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$).

第一行包含三个整数 $n$、$m$、$q$（$1 \leq n,m,q \leq 2 \cdot 10^5$）。

第二行包含一个长度为 $n$ 的二进制字符串 $s$，仅由数字 $0$ 和 $1$ 组成。

接下来 $m$ 行中的第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$）。

接下来 $q$ 行中的第 $i$ 行包含一个整数 $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.

输出 $q$ 个整数。其中第 $i$ 个整数表示：在第 $i$ 轮中，为使字符串 $s$ 变为字典序最大的可能字符串 $t(s)$ 所需执行的最少操作次数。

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.

在第一个测试用例中，

最初，$t(s) = s(1,2) + s(1,2) = 0101$。

执行第 $1$ 个查询后，$s$ 变为 $11$，因此 $t$ 变为 $1111$。此时无需执行任何操作，因为 $t(s)$ 已经是字典序最大的字符串。

执行第 $2$ 个查询后，$s$ 变为 $01$，因此 $t$ 变为 $0101$。你需要执行 $1$ 次操作：交换 $s_1$ 和 $s_2$。于是，$t(s)$ 变为 $1010$，这是你能得到的字典序最大的字符串。