标签:
难度: Hard
标签:
难度: Hard
运行时间: 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
这道题的题解采用了线段树(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
在线段树中,每个节点的值是根据其子节点的值通过特定的逻辑运算(此处为与非运算)计算得到的。与非运算是对其子区间内的所有元素进行的逐对逻辑运算。通过递归地将叶子节点(即原始数组元素)的与非结果合并,每个内部节点最终会反映出其所代表的子区间内所有元素的与非结果。这种自底向上的构建方法确保了从叶子节点到根节点,每个节点的值都精确地代表了对应区间内的运算结果。
当线段树的叶子节点发生更新时,影响会向上传播至根节点。具体来说,首先更新受影响的叶子节点,然后逐级向上更新其父节点。每个父节点的新值根据其两个子节点的值通过与非运算重新计算得出。这个更新过程重复进行,直到达到根节点。通过这种方式,可以确保所有受影响的内部节点的值都会被正确地更新,从而保持整个线段树的一致性和正确性。
与非运算的结果可能会随着运算次数的增加而变化,特别是在多次连续运算的情况下。在题解中,奇偶性的考虑基于与非运算的性质,即重复的与非运算可能会在一定的结果之间周期性地变化(例如,可能在两个特定的值之间切换)。因此,通过考虑运算次数的奇偶性,可以决定采用哪种计算模式,从而优化运算过程,避免不必要的重复计算。这种方法基于对运算结果周期性变化的观察和利用,是一种有效利用已有信息进行优化的策略。