P12758 [POI 2017 R3] 奇偶路口 Crossroads of parity

翻译来自于 [LibreOJ](https://loj.ac/p/5066)。

**题目译自 [XXIV Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi24-3/dashboard/) [Rozdroża parzystości](https://szkopul.edu.pl/problemset/problem/-7cqC3RrH4e-Ar7DWy4GKzLv/statement/)** Bajtazar 掌管拜托尼亚王国新设立的公国，辖内有 $n$ 座城市。公国尚在建设初期，尚未修筑任何道路。Bajtazar 规划了 $m$ 条双向道路，每条连接两座城市。若全部建成，可实现任意城市间连通。然而，他缺乏设计经验，道路规划效率低下，每条新路的建设难度远超之前所有道路之和。他估算第 $i$ 条路的建设成本为 $2^i$ 拜托币。 不幸的是，拜托尼亚掀起一股「奇偶」热潮，居民对道路数的奇偶性极度执着。部分城市的居民认为偶数道路象征和谐与平静，要求其城市连出的道路数为偶数；其他城市居民则视奇数为独立与活力的象征，要求道路数为奇数。 Bajtazar 需重新规划，选择部分道路，满足所有城市的奇偶要求，并尽量降低总成本。但拜托尼亚公共采购法有时要求剔除 $k-1$ 个最便宜的方案，因此他需构建满足居民要求的第 $k$ 便宜的道路网。注意，居民不再要求道路网连通所有城市，尽管原计划具备此特性，但奇偶要求可能与之冲突。 更糟的是，拜托尼亚议会频繁修改采购法，变更 $k$ 值，居民也常改变偏好，忽而崇尚偶数，忽而迷恋奇数。Bajtazar 必须随之调整规划。帮助他展现慷慨与高效的治理能力，适应居民多变的需求，设计应建的道路网！

第一行包含两个整数 $n, m$ $(1 \leq n, m \leq 500000)$，分别表示城市数量和可建道路数量。 接下来的 $m$ 行描述道路，第 $i$ 行包含两个整数 $a_i, b_i$ $(1 \leq a_i, b_i \leq n, a_i \neq b_i)$，表示可建连接城市 $a_i$ 和 $b_i$ 的双向道路，成本为 $2^i$ 拜托币。每对城市至多出现一次。 下一行包含 $n$ 个整数 $p_1, \ldots, p_n$，若 $p_i=0$，第 $i$ 个城市居民偏好偶数道路数；若 $p_i=1$，偏好奇数。 下一行包含整数 $k$ $(1 \leq k \leq 10^{18})$，表示 Bajtazar 考虑第 $k$ 便宜的满足居民要求的道路网（$k=1$ 为最便宜）。不同方案成本均不同。 下一行包含整数 $q$ $(0 \leq q \leq 500000)$，表示查询数量，随后 $q$ 行描述查询。每行包含字符 $c$ 和整数 $v$： - 若 $c=\texttt{M}$，城市 $v$ $(1 \leq v \leq n)$ 的居民改变偏好（偶变奇，奇变偶）。 - 若 $c=\texttt{K}$，采购法变更，Bajtazar 考虑第 $v$ $(1 \leq v \leq 10^{18})$ 便宜的道路网。 - 若 $c=\texttt{D}$，Bajtazar 询问当前道路网是否包含第 $v$ $(1 \leq v \leq m)$ 条路（成本 $2^v$）。

第一行输出初始道路网（居民偏好变更前），包含 $m$ 个整数，第 $i$ 个为 $1$ 表示建第 $i$ 条路，为 $0$ 表示不建，保证存在合法方案。 接下来的行对应 $c=\texttt{D}$ 的查询。若当前道路网不存在（因居民偏好变更或方案不足被剔除），输出 $-1$；若存在，输出 $1$ 表示当前方案包含第 $v$ 条路，输出 $0$ 表示不包含。

**样例 1 解释** 有三座城市和三条路形成环。最便宜的道路网满足城市 $1,2$ 奇数、城市 $3$ 偶数要求，仅包含路 $1-2$（成本 $2$）。不存在仅一个城市有奇数道路的方案。城市 $1,3$ 奇数、城市 $2$ 偶数的方案有两种：较便宜的包含路 $1-2, 2-3$（成本 $2+4=6$），较贵的包含路 $1-3$（成本 $8$）。 **附加样例** 1. $n=6, m=15, q=50$，每对城市间有路，无 $\texttt{K}$ 类型查询。 2. $n=10, m=10, q=84$，路形成环，$\texttt{D}$ 类型查询时总有两种可行方案。 3. $n=101, m=150$，$50$ 个三角形，每相邻三角形共享一顶点，全为偶数要求，$k=2^{50}$，无查询。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $k=1, q=0$（仅最便宜方案，无查询） | $32$ | | $2$ | $q=0$（无查询） | $25$ | | $3$ | 仅 $\texttt{M}$ 或 $\texttt{D}$ 类型查询 | $30$ | | $4$ | 无附加限制 | $13$ |