# 2次元Imos法 # テンプレート(自作): https://github.com/Rino-program/atcoder/blob/main/contests/.template/template.py class Imos2D: """概要: 2次元いもす法(差分グリッド)を扱うクラス。 メソッド: add(y1, x1, y2, x2, x): 矩形 [y1,y2)×[x1,x2) に x を加算予約する。 build(): 全予約を反映した最終グリッドを返す。 計算量: add は O(1)、build は O(HW)。 補足: 多数の矩形更新をまとめて処理したいときに有効。 使用例: imos = Imos2D(H, W) imos.add(y1, x1, y2, x2, 1) # [y1,y2) × [x1,x2) に +1 result = imos.build() """ def __init__(self, h: int, w: int): self.h = h self.w = w self.diff = [[0] * (w + 1) for _ in range(h + 1)] def add(self, y1: int, x1: int, y2: int, x2: int, x: int = 1) -> None: """[y1, y2) × [x1, x2) に x を加算(0-indexed)""" self.diff[y1][x1] += x self.diff[y1][x2] -= x self.diff[y2][x1] -= x self.diff[y2][x2] += x def build(self) -> list[list[int]]: """累積和を計算して結果を返す""" # 横方向 for i in range(self.h): for j in range(self.w): self.diff[i][j + 1] += self.diff[i][j] # 縦方向 for j in range(self.w): for i in range(self.h): self.diff[i + 1][j] += self.diff[i][j] return [row[:self.w] for row in self.diff[:self.h]] H, W, N = map(int, input().split()) imos = Imos2D(H, W) for _ in range(N): y1, x1, y2, x2 = map(int, input().split()) imos.add(y1 - 1, x1 - 1, y2, x2) result = imos.build() ans = 0 for row in result: ans += sum(1 if x <= 0 else 0 for x in row) print(ans)