QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100
Statistics

对于一个 $n \times m$ 的 01 矩阵 $A$(下标从 1 开始,下同),定义一个 $n \times m$ 的 01 矩阵 $B$ 是好的当且仅当:

  1. 对于第 $i \;(1 \le i \le n)$ 行,不存在 $1 \le j,k \le m, j \neq k$ 同时满足: $$ A_{i,j} = B_{i,k} = 1, \quad A_{i,k} = B_{i,j} = 0 $$

  2. 对于第 $i \;(1 \le i \le m)$ 列,不存在 $1 \le j,k \le n, j \neq k$ 同时满足: $$ A_{j,i} = B_{j,i} = 1, \quad A_{k,i} = B_{k,i} = 0 $$

初始 $B$ 矩阵所有位置为 0,每次可以选择若干个位置,将它们同时变成 1。要求做完操作后,矩阵 $B$ 仍然是好的。设最多执行 $k$ 次操作,则矩阵 $A$ 的权值为 $k$。

小 █ 现在有一个 $N \times N$ 的 01 矩阵 $M$。由于 $N$ 很大,所以 $M$ 由特殊方式生成。

初始 $M$ 中所有位置均为 0,有 $Q$ 次修改操作。每次操作给定 $x_1, x_2, y_1, y_2$,对于满足 $x_1 \le i \le x_2$ 且 $y_1 \le j \le y_2$ 的所有位置 $(i, j)$,将 $M_{i,j}$ 变为 $1 - M_{i,j}$。

定义 $S_{i,j}$ 为 $M$ 前 $i$ 行前 $j$ 列构成的子矩阵的权值。

输入格式

第一行三个数 $N, Q, op$。

接下来 $Q$ 行,每行四个数 $x_1, x_2, y_1, y_2$。

输出格式

若 $op = 0$,输出一个数 $S_{N,N}$。

若 $op = 1$,输出一行 $N$ 个数,分别是 $S_{N,1}, S_{N,2}, \cdots, S_{N,N}$。

输入输出样例

样例输入 1

2 2 1
1 1 1 1
2 2 2 2

样例输出 1

2 1

样例 2 & 3

详见下发文件。

数据范围

Subtask 编号 分值 $N \le$ 特殊性质
1 5 4 A
2 10 50
3 10 5000
4 10
5 15 $2 \times 10^5$ B
6 15 A
7 35
  • 特殊性质 A:保证 $op = 0$。
  • 特殊性质 B:一次操作的代价为 $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$,所有操作的代价之和 $\le 2 \times 10^6$。

对于所有数据,保证: $$ 1 \le N, Q \le 2 \times 10^5, \quad 1 \le x_1 \le x_2 \le N, \quad 1 \le y_1 \le y_2 \le N, \quad op \in \{0, 1\} $$