P16084 [ICPC 2024 NAC] Comparator

许多编程语言允许你定义自定义比较器来对用户定义的对象进行排序。 IFFY 是一种编程语言，其中的唯一程序是被设计用作比较器的函数。这些函数操作于比特串（下文称为“字”）。字从最左边的字符开始以 1 为下标索引。 要在 IFFY 中编写一个作用于两个字的函数，程序员需要编写一系列 if 语句。每个 if 语句从第一个字中选择一个比特，从第二个字中选择一个比特，并计算这两个比特上的某个表达式。如果在该选定的比特上表达式的值为 $1$，则函数立即返回指定的返回值。否则，执行流落到下一个 if 语句，不返回任何值。 每个 if 语句的语法是 `a b expr r`，其中整数 $a$ 指定第一个字中的比特位置，整数 $b$ 指定第二个字中的比特位置，$expr$ 是使用变量 $x$ 和/或 $y$ 的布尔表达式，$r$（$0$ 或 $1$）是当表达式值为 $1$ 时函数返回的值。变量 $x$ 指代第一个字中指定的比特，变量 $y$ 指代第二个字中指定的比特。例如，考虑 if 语句 `2 3 x|y 0`。这个表达式意味着：如果第一个字的第 2 个比特或第二个字的第 3 个比特被置为 1，则返回 $0$，否则继续执行下一个语句。 有效表达式的语法如下： - `x`、`y`、`0` 和 `1` 是有效表达式。 - 如果 $E$ 是有效表达式，则 `(E)` 是有效表达式。 - 如果 $E$ 是有效表达式，则 `!E` 是有效表达式。 - 如果 $E_1$ 和 $E_2$ 是有效表达式，则形如 `E1 BIN_OP E2` 的所有字符串都是有效表达式，其中 `BIN_OP` 是 `=`（等于）、`&`（与）、`|`（或）或 `^`（异或）之一。 括号优先级最高，其次是一元 `!`，再其次是二元 `=`、`&`、`|` 和 `^`，按此顺序。所有二元运算符都是左结合的。 以下是每个运算符的真值表： | $ x $ | $ !\,x $ | |:-:|:-:| | $ 0 $ | $ 1 $ | | $ 1 $ | $ 0 $ | 图 C.1：唯一一元运算符的真值表。 | $ x $ | $ y $ | $ x = y $ | |:-:|:-:|:-:| | $ 0 $ | $ 0 $ | $ 1 $ | | $ 0 $ | $ 1 $ | $ 0 $ | | $ 1 $ | $ 0 $ | $ 0 $ | | $ 1 $ | $ 1 $ | $ 1 $ | | $ x $ | $ y $ | $ x \& y $ | |:-:|:-:|:-:| | $ 0 $ | $ 0 $ | $ 0 $ | | $ 0 $ | $ 1 $ | $ 0 $ | | $ 1 $ | $ 0 $ | $ 0 $ | | $ 1 $ | $ 1 $ | $ 1 $ | | $ x $ | $ y $ | $ x \vert y $ | |:-:|:-:|:-:| | $ 0 $ | $ 0 $ | $ 0 $ | | $ 0 $ | $ 1 $ | $ 1 $ | | $ 1 $ | $ 0 $ | $ 1 $ | | $ 1 $ | $ 1 $ | $ 1 $ | | $ x $ | $ y $ | $ x \hat{\ } y $ | |:-:|:-:|:-:| | $ 0 $ | $ 0 $ | $ 0 $ | | $ 0 $ | $ 1 $ | $ 1 $ | | $ 1 $ | $ 0 $ | $ 1 $ | | $ 1 $ | $ 1 $ | $ 0 $ | 图 C.2：二元运算符的真值表。 要使函数 $ f(x, y) $ 能够作为比较器正常运作，它必须满足某些性质。非正式地说，对于 $ f(x, y) $ 作为比较器，它应当施加某种序关系 $ < $，使得 $ f(x, y) $ 返回 $ 1 $ 当且仅当 $ x < y $。例如，样例 1 是一个有效的比较器，用于对长度为 2 的比特串进行排序。更正式地说，比较器必须满足的三个性质是自反性、对称性和传递性，具体如下： 1. **自反性**：对于所有 $ x $，$ f(x, x) $ 应返回 $ 0 $。 2. **对称性**：对于所有 $ x, y $，如果 $ f(x, y) $ 返回 $ 1 $，则 $ f(y, x) $ 必须返回 $ 0 $。 3. **传递性**：对于所有 $ x, y, z $，如果 $ f(x, y) $ 和 $ f(y, z) $ 都返回 $ 1 $，则 $ f(x, z) $ 也必须返回 $ 1 $。 给定一个用 IFFY 语言编写的函数，请通过计算这三个性质被违反的次数来衡量它满足这些性质的程度。首先，对于给定长度的所有字，统计自反性失效的字数。其次，统计对称性失效的字对数。最后，统计传递性失效的字三元组数。

输入的第一行包含两个整数 $ n $（$ 0 \le n \le 2 \cdot 10^5 $）和 $ k $（$ 1 \le k \le 10 $），其中 $ n $ 是函数中 if 语句的行数，$ k $ 是被比较的值的比特数。 接下来的 $ n $ 行，每行包含四个形如 `a b expr r` 的标记，其中 $ a $ 和 $ b $（$ 1 \le a, b \le k $）是要考虑的 $ x $ 和 $ y $ 中的比特索引，`expr` 是一个有效表达式，$ r $（$ 0 \le r \le 1 $）是返回值。最后一行给出如果没有 if 语句被触发时的返回值。所有表达式的总长度不超过 $ 10^6 $。

输出一行，包含三个空格分隔的整数。第一个整数是自反性被违反的字数，第二个整数是对称性被违反的字对数，第三个整数是传递性被违反的字三元组数。

翻译由 DeepSeek V3.2 完成