二维差分
题目很明显要维护每个格子被操作了多少次,记作cnt
- 如果
cnt
为奇数,则输出1
- 如果
cnt
为偶数,则输出0
等价于cnt & 1
这又涉及到区间加操作
这很自然地就能想到要用差分数组来做这道题
n, m = map(int, input().split())
d = [[0] * (n + 2) for _ in range(n + 2)] # 二维差分数组
for _ in range(m): # 区域 +
x1, y1, x2, y2 = map(int, input().split())
d[x1][y1] += 1
d[x1][y2 + 1] -= 1
d[x2 + 1][y1] -= 1
d[x2 + 1][y2 + 1] += 1
for i in range(1, n + 1):
for j in range(1, n + 1): # 查询
d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]
print(d[i][j] & 1, end='')
print()
复杂度分析
- 时间复杂度:$O(m + n ^ 2)$
- 空间复杂度:$O(n ^ 2)$,差分数组的空间
咱们一模一样的代码为啥我这里有这个报错哎
File “a.py”, line 12
print(d[i][j] & 1, end=’‘)
^
SyntaxError: invalid syntax (expected ‘)’)
SyntaxError: invalid syntax (expected ‘)’)说你少了个括号。。因为你end=‘’后面的引号用了中文的了。。