Logical Moos

题目描述

农夫约翰有一个由 $N$ 个关键字组成的布尔语句（$1 \leq N < 2 \cdot 10^5$，$N$ 为奇数）。在奇数位置上只会出现 $\texttt{true}$ 或 $\texttt{false}$，而在偶数位置上只会出现 $\texttt{and}$ 和 $\texttt{or}$。

形如 $x\text{ OPERATOR }y$ 的短语，其中 $x$ 和 $y$ 都是 $\texttt{true}$ 或 $\texttt{false}$，且 $\text{OPERATOR}$ 为 $\texttt{and}$ 或 $\texttt{or}$，其计算规则如下： $x\texttt{ and }y$：当且仅当 $x$ 与 $y$ 都为 true 时结果为 true，否则为 false。 $x\texttt{ or }y$：当 $x$ 或 $y$ 至少一个为 true 时结果为 true，否则为 false。

计算整个语句时，FJ 需要考虑 Moo Language 的运算优先级。与 C++ 类似，$\texttt{and}$ 的优先级高于 $\texttt{or}$。更具体地，为了计算该语句，重复执行以下步骤，直到语句只剩下一个关键字： 如果语句中包含 $\texttt{and}$，任选其中一个，并将其两侧的短语用计算结果替换。 否则，语句中包含 $\texttt{or}$。任选其中一个，并将其两侧的短语用计算结果替换。

可以证明：在某一步中如果有多个短语可以被计算，选择哪一个并不影响最终结果；该语句总会计算得到相同的值。

FJ 有 $Q$ 个查询（$1 \leq Q \leq 2 \cdot 10^5$）。在每个查询中，他给出两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq N$，$l$ 和 $r$ 均为奇数），并删除从第 $l$ 个关键字到第 $r$ 个关键字（含）这一段。随后，他希望用一个简单的 $\texttt{true}$ 或 $\texttt{false}$ 来替换刚刚删除的整段，使得整个语句最终计算为某个指定的布尔值。请你判断这是否可能！

输入格式

第一行包含 $N$ 和 $Q$。 第二行包含 $N$ 个字符串，表示一个合法的布尔语句。 接下来 $Q$ 行每行包含两个整数 $l$ 和 $r$，以及一个字符串 $\texttt{true}$ 或 $\texttt{false}$，表示他希望整个语句最终计算为 true 还是 false。

输出格式

输出一个长度为 $Q$ 的字符串，其中第 $i$ 个字符若第 $i$ 个查询可行则为 Y，否则为 N。

5 7
false and true or true
1 1 false
1 3 true
1 5 false
3 3 true
3 3 false
5 5 false
5 5 true

NYYYNYY

13 4
false or true and false and false and true or true and false
1 5 false
3 11 true
3 11 false
13 13 true

YNYY

提示

我们来分析第一个查询： 如果我们删除区间 $[1, 1]$ 并用 $\texttt{true}$ 替换，那么整个语句变为： true and true or true 我们计算位置 $2$ 的 $\texttt{and}$ 关键字，得到： true or true 由于不再有 $\texttt{and}$ 关键字，我们必须计算 $\texttt{or}$ 关键字。计算后，剩下的是： true 可以证明：如果我们用 $\texttt{false}$ 替换该区间，语句仍会计算为 $\texttt{true}$，因此输出 N，因为语句不可能计算为 $\texttt{false}$。 对于第二个查询，我们可以将区间 $[1, 3]$ 替换为 $\texttt{true}$，整个语句将计算为 $\texttt{true}$，因此输出 Y。 对于第三个查询，由于 $[1, 5]$ 是整个语句，我们可以用任何值替换，所以输出 Y。

评分： 输入 3-5：$N,Q\le 10^2$ 输入 6-8：$N,Q\le 10^3$ 输入 9-26：无额外限制。 题目来源：Chongtian Ma

标签: USACO|2024|Bronze

来源

USACO|2024|Bronze