P10626 [JOI Open 2024] 考试 2 / Examination 2

JOI 君在 IOI 高中上学，期末考试即将来临。考试的内容是计算 **IOI 函数**。IOI 函数是将 $[1,10^9]$ 之间的整数映射到布尔值（即 $\texttt{True}/\texttt{False}$）的函数。IOI 函数可以从以下六条 IOI 高中规定的规则中构造： 1. 设 $a$ 为 $[1,10^9]$ 之间的整数，则 $\texttt{[a]}$ 是一个 IOI 函数。它将不小于 $a$ 的整数映射成 $\texttt{True}$，将小于 $a$ 的整数映射成 $\texttt{False}$。 2. 记 $\texttt{f}$ 为 IOI 函数，则 $\texttt{(f)}$ 是一个 IOI 函数，它的映射规则与 $\texttt{f}$ 的映射规则相同。 3. 记 $\texttt{f}$ 为 IOI 函数，则 $\texttt{!f}$ 是一个 IOI 函数。设 $x$ 为整数，若 $\texttt{f}$ 将 $x$ 映射为 $\texttt{True}$，则 $\texttt{!f}$ 将 $x$ 映射为 $\texttt{False}$；否则 $\texttt{!f}$ 将 $x$ 映射为 $\texttt{True}$。 4. 记 $\texttt{f},\texttt{g}$ 为 IOI 函数，则 $\texttt{f\&g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\texttt{f\&g}$ 将 $x$ 映射为 $\texttt{True}$，当且仅当 $\texttt{f},\texttt{g}$ 都将 $x$ 映射为 $\texttt{True}$。 5. 记 $\texttt{f},\texttt{g}$ 为 IOI 函数，则 $\texttt{f\^ g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\texttt{f\^ g}$ 将 $x$ 映射为 $\texttt{True}$，当且仅当 $\texttt{f},\texttt{g}$ 中恰好有一个将 $x$ 映射为 $\texttt{True}$。 6. 记 $\texttt{f},\texttt{g}$ 为 IOI 函数，则 $\texttt{f|g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\texttt{f|g}$ 将 $x$ 映射为 $\texttt{True}$，当且仅当 $\texttt{f},\texttt{g}$ 中至少有一个将 $x$ 映射为 $\texttt{True}$。 如果某个 IOI 函数用多条规则构造出，数字更大的规则将决定函数值。例如，对于 $\texttt{[1]\&[2]|[3]}$ 应当应用规则 6，其中 $\texttt{f} = \texttt{[1]\&[2]},\texttt{g} = \texttt{[3]}$（而非应用规则 4，其中 $\texttt{f} = \texttt{[1]},\texttt{g} = \texttt{[2]|[3]}$）。额外地，对于规则 4，5，6，应当最大化 $\texttt{f}$ 的长度。例如，对于 $\texttt{[4]ˆ[5]ˆ[6]}$，应当在 $\texttt{f} = \texttt{[4]ˆ[5]},\texttt{g} = \texttt{[6]}$ 上应用规则 5（而非 $\texttt{f} = \texttt{[4]},\texttt{g} = \texttt{[5]ˆ[6]}$）。 为备战期末考试，JOI 君准备好了一个长度为 $N$ 的 IOI 函数 $S$。他打算用 $Q$ 个整数 $X_1,X_2,\cdots,X_Q$ 来练习他的计算技能。于是他找来了你——能够熟练处理 IOI 函数的人，来解决这个问题。 你需要写一个程序。给定 $N,Q,S$ 以及 $X_1,X_2,\cdots,X_Q$，对于 $i=1,2=\cdots,Q$，回答 IOI 函数 $S$ 会将 $X_i$ 映射成 $\texttt{True}$ 还是 $\texttt{False}$。

输入格式如下所示： > $N$ $Q$\ > $S$\ > $X_1$\ > $X_2$\ > $\vdots$\ > $X_Q$

输出 $Q$ 行，第 $i$ 行为 $\texttt{True}$ 或者 $\texttt{False}$，即 $X_i$ 被 $S$ 映射成的值。

### 样例解释 样例 $1$ 解释如下： | $X_i$ | $\texttt{![2]}$ | $\texttt{[3]}$ | $\texttt{![2]\char124[3]}$ | $\texttt{![4]}$ | $\texttt{(![2]\char124[3])\&![4]}$ | | :--: | :--: | :--: | :--: | :--: | :--: | | $1$ | $\texttt{True}$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{True}$ | | $2$ | $\texttt{False}$ | $\texttt{False}$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{False}$ | | $3$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{True}$ | | $4$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{False}$ | $\texttt{False}$ | | $5$ | $\texttt{False}$ | $\texttt{True}$ | $\texttt{True}$ | $\texttt{False}$ | $\texttt{False}$ | 样例 $1$ 满足子任务 $3,6,7$ 的条件。 样例 $2$ 满足子任务 $1,3,5\sim 7$ 的条件。 样例 $3$ 满足子任务 $3,4,6,7$ 的条件。 ### 数据范围 - $1 \le N \le 1\,000\,000$； - $1 \le Q \le 200\,000$； - $S$ 为长度为 $N$ 的 IOI 函数； - $1 \le X_i \le 10^9$（$1 \le i \le Q$）； - $N, Q, X_i$（$1 \le i \le Q$）均为整数。 ### 子任务 1. （$5$ points）$S$ 中不含 $\texttt{\&}$ 和 $\texttt{|}$； 2. （$20$ points）$Q = 1$； 3. （$10$ points）$N \le 10\,000$； 4. （$6$ points）$S$ 中不含 $\texttt{!}$ 和 $\texttt{ˆ}$； 5. （$12$ points）当应用规则 4 或 6 来构造 $S$ 时，$\texttt{f}$ 和 $\texttt{g}$ 中至少有一个是用规则 1 得到的； 6. （$20$ points）$N \le 400\, 000$； 7. （$27$ points）无额外约束。 *赛时公告：如果你复制题面中的 LaTeX，可能会得到 `ˆ`，但实际上是 `^`。请特别注意。 由 Starrykiller 根据英文题面翻译。