{"problem":{"name":"[JOI Open 2024] 考试 2 / Examination 2","description":{"content":"JOI 君在 IOI 高中上学，期末考试即将来临。考试的内容是计算 **IOI 函数**。IOI 函数是将 $[1,10^9]$ 之间的整数映射到布尔值（即 $\\texttt{True}/\\texttt{False}$）的函数。IOI 函数可以从以下六条 IOI 高中规定的规则中构造： 1. 设 $a$ 为 $[1,10^9]$ 之间的整数，则 $\\texttt{[a]}$ 是一个 IOI 函数","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10626"},"statements":[{"statement_type":"Markdown","content":"JOI 君在 IOI 高中上学，期末考试即将来临。考试的内容是计算 **IOI 函数**。IOI 函数是将 $[1,10^9]$ 之间的整数映射到布尔值（即 $\\texttt{True}/\\texttt{False}$）的函数。IOI 函数可以从以下六条 IOI 高中规定的规则中构造：\n\n1. 设 $a$ 为 $[1,10^9]$ 之间的整数，则 $\\texttt{[a]}$ 是一个 IOI 函数。它将不小于 $a$ 的整数映射成 $\\texttt{True}$，将小于 $a$ 的整数映射成 $\\texttt{False}$。\n\n2. 记 $\\texttt{f}$ 为 IOI 函数，则 $\\texttt{(f)}$ 是一个 IOI 函数，它的映射规则与 $\\texttt{f}$ 的映射规则相同。\n\n3. 记 $\\texttt{f}$ 为 IOI 函数，则 $\\texttt{!f}$ 是一个 IOI 函数。设 $x$ 为整数，若 $\\texttt{f}$ 将 $x$ 映射为 $\\texttt{True}$，则 $\\texttt{!f}$ 将 $x$ 映射为 $\\texttt{False}$；否则 $\\texttt{!f}$ 将 $x$ 映射为 $\\texttt{True}$。\n\n4. 记 $\\texttt{f},\\texttt{g}$ 为 IOI 函数，则 $\\texttt{f\\&g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\\texttt{f\\&g}$ 将 $x$ 映射为 $\\texttt{True}$，当且仅当 $\\texttt{f},\\texttt{g}$ 都将 $x$ 映射为 $\\texttt{True}$。\n\n5. 记 $\\texttt{f},\\texttt{g}$ 为 IOI 函数，则 $\\texttt{f\\^ g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\\texttt{f\\^ g}$ 将 $x$ 映射为 $\\texttt{True}$，当且仅当 $\\texttt{f},\\texttt{g}$ 中恰好有一个将 $x$ 映射为 $\\texttt{True}$。\n\n6. 记 $\\texttt{f},\\texttt{g}$ 为 IOI 函数，则 $\\texttt{f|g}$ 也是一个 IOI 函数。设 $x$ 为整数，则 $\\texttt{f|g}$ 将 $x$ 映射为 $\\texttt{True}$，当且仅当 $\\texttt{f},\\texttt{g}$ 中至少有一个将 $x$ 映射为 $\\texttt{True}$。\n\n如果某个 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]}$）。\n\n为备战期末考试，JOI 君准备好了一个长度为 $N$ 的 IOI 函数 $S$。他打算用 $Q$ 个整数 $X_1,X_2,\\cdots,X_Q$ 来练习他的计算技能。于是他找来了你——能够熟练处理 IOI 函数的人，来解决这个问题。\n\n你需要写一个程序。给定 $N,Q,S$ 以及 $X_1,X_2,\\cdots,X_Q$，对于 $i=1,2=\\cdots,Q$，回答 IOI 函数 $S$ 会将 $X_i$ 映射成 $\\texttt{True}$ 还是 $\\texttt{False}$。\n\n## Input\n\n输入格式如下所示：\n\n> $N$ $Q$\\\n> $S$\\\n> $X_1$\\\n> $X_2$\\\n> $\\vdots$\\\n> $X_Q$\n\n## Output\n\n输出 $Q$ 行，第 $i$ 行为 $\\texttt{True}$ 或者 $\\texttt{False}$，即 $X_i$ 被 $S$ 映射成的值。\n\n[samples]\n\n## Note\n\n### 样例解释\n\n样例 $1$ 解释如下：\n\n| $X_i$ | $\\texttt{![2]}$ | $\\texttt{[3]}$ | $\\texttt{![2]\\char124[3]}$ | $\\texttt{![4]}$ | $\\texttt{(![2]\\char124[3])\\&![4]}$ |\n| :--: | :--: | :--: | :--: | :--: | :--: |\n| $1$ | $\\texttt{True}$ | $\\texttt{False}$ | $\\texttt{True}$ | $\\texttt{True}$ | $\\texttt{True}$ |\n| $2$ | $\\texttt{False}$ | $\\texttt{False}$ | $\\texttt{False}$ | $\\texttt{True}$ | $\\texttt{False}$ |\n| $3$ |  $\\texttt{False}$ | $\\texttt{True}$ | $\\texttt{True}$ | $\\texttt{True}$ | $\\texttt{True}$ |\n| $4$ | $\\texttt{False}$ | $\\texttt{True}$ | $\\texttt{True}$ | $\\texttt{False}$ | $\\texttt{False}$ |\n| $5$ |  $\\texttt{False}$ | $\\texttt{True}$ | $\\texttt{True}$ | $\\texttt{False}$ | $\\texttt{False}$ |\n\n样例 $1$ 满足子任务 $3,6,7$ 的条件。\n\n样例 $2$ 满足子任务 $1,3,5\\sim 7$ 的条件。\n\n样例 $3$ 满足子任务 $3,4,6,7$ 的条件。\t\n\n### 数据范围\n\n- $1 \\le N \\le 1\\,000\\,000$；\n- $1 \\le Q \\le 200\\,000$；\n- $S$ 为长度为 $N$ 的 IOI 函数；\n- $1 \\le X_i \\le 10^9$（$1 \\le i \\le Q$）；\n- $N, Q, X_i$（$1 \\le i \\le Q$）均为整数。\n\n### 子任务\n\n1. （$5$ points）$S$ 中不含 $\\texttt{\\&}$ 和 $\\texttt{|}$；\n2. （$20$ points）$Q = 1$；\n3. （$10$ points）$N \\le 10\\,000$；\n4. （$6$ points）$S$ 中不含 $\\texttt{!}$ 和 $\\texttt{ˆ}$；\n5. （$12$ points）当应用规则 4 或 6 来构造 $S$ 时，$\\texttt{f}$ 和 $\\texttt{g}$ 中至少有一个是用规则 1 得到的；\n6. （$20$ points）$N \\le 400\\, 000$；\n7. （$27$ points）无额外约束。\n\n*赛时公告：如果你复制题面中的 LaTeX，可能会得到 `ˆ`，但实际上是 `^`。请特别注意。\n\n由 Starrykiller 根据英文题面翻译。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10626","tags":["动态规划 DP","线段树","树上启发式合并","2024","树链剖分","动态树 LCT","JOI（日本）"],"sample_group":[["15 5\n(![2]|[3])&![4]\n1\n2\n3\n4\n5","True\nFalse\nTrue\nFalse\nFalse"],["20 4\n(!![23])^((([116])))\n54\n1\n200\n89","True\nFalse\nFalse\nTrue"],["32 4\n[2]|[5]&[1]|(([1000000000])|[7])\n4\n10\n6\n1","True\nTrue\nTrue\nFalse"]],"created_at":"2026-03-03 11:09:25"}}