CF1847D Professor Higashikata

Josuke 厌倦了在杜王町的平静生活。为了追随他的侄子 Jotaro 的脚步，他决定努力学习，成为一名计算机科学教授。在网上查找竞赛编程题目的时候，他遇到了如下问题： 给定一个长度为 $n$ 的二进制字符串 $s$。对 $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$。定义 $t(s) = t_1 + t_2 + \ldots + t_m$，即按顺序将 $t_i$ 连接起来。 有 $q$ 次对字符串的更新。在第 $i$ 次更新中，将 $s_{x_i}$ 取反。也就是说，如果 $s_{x_i}=1$，则变为 $0$，反之亦然。每次更新后，求最少需要多少次操作才能使 $t(s)$ 字典序最大。 注意，实际上并不需要真正执行操作，只需输出操作次数。 请帮助 Josuke 实现他的梦想，解决这个问题。 —————————————————————— $^\dagger$ 字符串 $a$ 是字符串 $b$ 的子串，如果 $a$ 可以通过删除 $b$ 开头若干（可能为零或全部）字符和结尾若干（可能为零或全部）字符得到。 $^\ddagger$ 对于长度相同的字符串 $a$ 和 $b$，如果在第一个不同的位置，$a$ 为 $1$，$b$ 为 $0$，则 $a$ 的字典序大于 $b$。

第一行包含三个整数 $n$、$m$、$q$（$1 \leq n, m, q \leq 2 \times 10^5$）。 第二行包含一个长度为 $n$ 的二进制字符串 $s$，仅由 $0$ 和 $1$ 组成。 接下来 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$）。 接下来 $q$ 行，每行包含一个整数 $x_i$（$1 \leq x_i \leq n$）。

输出 $q$ 个整数，第 $i$ 个整数表示在第 $i$ 轮更新后，为了使 $t(s)$ 的字典序最大，最少需要进行的操作次数。

在第一个测试样例中： 最初，$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$，这是可以达到的字典序最大字符串。 由 ChatGPT 4.1 翻译