与非的谜题

标签:

难度: Hard

在永恒之森中，封存着有关万灵之树线索的卷轴，只要探险队通过最后的考验，便可以获取前往万灵之树的线索。 探险队需要从一段不断变化的谜题数组中找到最终的密码，初始的谜题为长度为 `n` 的数组 `arr`（下标从 0 开始），数组中的数字代表了 `k` 位二进制数。 破解谜题的过程中，需要使用 `与非（NAND）` 运算方式，`operations[i] = [type,x,y]` 表示第 `i` 次进行的谜题操作信息： - 若 `type = 0`，表示修改操作，将谜题数组中下标 `x` 的数字变化为 `y`； - 若 `type = 1`，表示运算操作，将数字 `y` 进行 `x*n` 次「与非」操作，第 `i` 次与非操作为 `y = y NAND arr[i%n]`； > 运算操作结果即：`y NAND arr[0%n] NAND arr[1%n] NAND arr[2%n] ... NAND arr[(x*n-1)%n]` 最后，将所有运算操作的结果按顺序逐一进行 `异或（XOR）`运算，从而得到最终解开封印的密码。请返回最终解开封印的密码。 **注意:** - 「与非」（NAND）的操作为：先进行 `与` 操作，后进行 `非` 操作。 > 例如：两个三位二进制数`2`和`3`，其与非结果为 `NOT ((010) AND (011)) = (101) = 5` **示例 1：** > 输入: > `k = 3` > `arr = [1,2]` > `operations = [[1,2,3],[0,0,3],[1,2,2]]` > > 输出: `2` > > 解释： > 初始的谜题数组为 [1,2]，二进制位数为 3， > 第 0 次进行运算操作，将数字 3(011) 进行 2\*2 次「与非」运算， > 运算操作结果为 `3 NAND 1 NAND 2 NAND 1 NAND 2 = 5` > 第 1 次进行修改操作，谜题数组的第 `0` 个数字变化为 `3`，谜题变成 `[3,2]` > 第 2 次进行运算操作，将数字 2(010) 进行 2\*2 次「与非」运算， > 运算操作结果为 `2 NAND 3 NAND 2 NAND 3 NAND 2 = 7` > 所有运算操作结果进行「异或」运算为 `5 XOR 7 = 2` > 因此得到的最终密码为 `2`。 **示例 2：** > 输入: > `k = 4` > `arr = [4,6,4,7,10,9,11]` > `operations = [[1,5,7],[1,7,14],[0,6,7],[1,6,5]]` > 输出: `9` > 解释: > 初始的谜题数组为 [4,6,4,7,10,9,11], > 第 0 次进行运算操作，运算操作结果为 5； > 第 1 次进行运算操作，运算操作结果为 5； > 第 2 次进行修改操作，修改后谜题数组为 [4, 6, 4, 7, 10, 9, 7]； > 第 3 次进行运算操作，运算操作结果为 9； > 所有运算操作结果进行「异或」运算为 `5 XOR 5 XOR 9 = 9`； > 因此得到的最终密码为 `9`。 **提示:** - `1 <= arr.length, operations.length <= 10^4` - `1 <= k <= 30` - `0 <= arr[i] < 2^k` - 若 `type = 0`，`0 <= x < arr.length` 且 `0 <= y < 2^k` - 若 `type = 1`，`1 <= x < 10^9` 且 `0 <= y < 2^k` - 保证存在 `type = 1` 的操作

Submission

运行时间: 392 ms

内存: 22.1 MB

class Solution:
    def getNandResult(self, k: int, arr: List[int], operations: List[List[int]]) -> int:
        n, res = len(arr), 0
        m = 2**ceil(log2(n))
        s = 2**k-1
        tree = [0]*m*2
        for i in arr:
            tree.extend([s, i^s])
        tree.extend([0, s]*(m-n))
        for i in range(m-1, 0, -1):
            tree[i*2] = (tree[i*4+3]&tree[i*4])|(tree[i*4+2]&(~tree[i*4]))
            tree[i*2+1] = (tree[i*4+3]&tree[i*4+1])|(tree[i*4+2]&(~tree[i*4+1]))
        for t, x, y in operations:
            if t == 0:
                i = x+m
                tree[i*2] = s
                tree[i*2+1] = y^s
                while i >= 2:
                    i //= 2
                    a, b = tree[i*2], tree[i*2+1]
                    tree[i*2] = (tree[i*4+3]&tree[i*4])|(tree[i*4+2]&(~tree[i*4]))
                    tree[i*2+1] = (tree[i*4+3]&tree[i*4+1])|(tree[i*4+2]&(~tree[i*4+1]))
                    if tree[i*2] == a and tree[i*2+1] == b:
                        break
            else:
                r = (tree[3]&y)|(tree[2]&(~y))
                res ^= r if x%2 else (tree[3]&r)|(tree[2]&(~r))
        return res

Explain

这道题的题解采用了线段树(segment tree)的数据结构来高效地处理数组中的与非(NAND)运算。首先，构造一个线段树，其中每个节点代表一个区间的与非运算结果。线段树的大小是2倍的最接近n的2的幂的大小。在构造过程中，每个叶子节点存储与非运算的初始结果，而内部节点存储子区间的与非运算结果。接着，对于每个操作，如果是修改操作(type=0)，则更新线段树中相应的叶子节点，并向上更新所有影响到的内部节点。如果是运算操作(type=1)，则根据运算次数的奇偶性，从根节点开始计算与非运算的结果，并将结果异或到最终答案中。

时间复杂度: O(n + m log n)

空间复杂度: O(n)

class Solution:
    def getNandResult(self, k: int, arr: List[int], operations: List[List[int]]) -> int:
        n, res = len(arr), 0
        m = 2**ceil(log2(n))
        s = 2**k-1
        tree = [0]*m*2
        for i in arr:
            tree.extend([s, i^s])
        tree.extend([0, s]*(m-n))
        for i in range(m-1, 0, -1):
            tree[i*2] = (tree[i*4+3]&tree[i*4])|(tree[i*4+2]&(~tree[i*4]))
            tree[i*2+1] = (tree[i*4+3]&tree[i*4+1])|(tree[i*4+2]&(~tree[i*4+1]))
        for t, x, y in operations:
            if t == 0:
                i = x+m
                tree[i*2] = s
                tree[i*2+1] = y^s
                while i >= 2:
                    i //= 2
                    a, b = tree[i*2], tree[i*2+1]
                    tree[i*2] = (tree[i*4+3]&tree[i*4])|(tree[i*4+2]&(~tree[i*4]))
                    tree[i*2+1] = (tree[i*4+3]&tree[i*4+1])|(tree[i*4+2]&(~tree[i*4+1]))
                    if tree[i*2] == a and tree[i*2+1] == b:
                        break
            else:
                r = (tree[3]&y)|(tree[2]&(~y))
                res ^= r if x%2 else (tree[3]&r)|(tree[2]&(~r))
        return res

Explore

在线段树中，每个节点的值是根据其子节点的值通过特定的逻辑运算(此处为与非运算)计算得到的。与非运算是对其子区间内的所有元素进行的逐对逻辑运算。通过递归地将叶子节点(即原始数组元素)的与非结果合并，每个内部节点最终会反映出其所代表的子区间内所有元素的与非结果。这种自底向上的构建方法确保了从叶子节点到根节点，每个节点的值都精确地代表了对应区间内的运算结果。

当线段树的叶子节点发生更新时，影响会向上传播至根节点。具体来说，首先更新受影响的叶子节点，然后逐级向上更新其父节点。每个父节点的新值根据其两个子节点的值通过与非运算重新计算得出。这个更新过程重复进行，直到达到根节点。通过这种方式，可以确保所有受影响的内部节点的值都会被正确地更新，从而保持整个线段树的一致性和正确性。

与非运算的结果可能会随着运算次数的增加而变化，特别是在多次连续运算的情况下。在题解中，奇偶性的考虑基于与非运算的性质，即重复的与非运算可能会在一定的结果之间周期性地变化（例如，可能在两个特定的值之间切换）。因此，通过考虑运算次数的奇偶性，可以决定采用哪种计算模式，从而优化运算过程，避免不必要的重复计算。这种方法基于对运算结果周期性变化的观察和利用，是一种有效利用已有信息进行优化的策略。