对于一个 n×m 的 01
矩阵 A(下标从 1 开始,下同),定义一个 n×m 的 01
矩阵 B 是好的当且仅当:
对于第 i(1≤i≤n) 行,不存在 1≤j,k≤m,j≠k 同时满足: Ai,j=Bi,k=1,Ai,k=Bi,j=0
对于第 i(1≤i≤m) 列,不存在 1≤j,k≤n,j≠k 同时满足: Aj,i=Bj,i=1,Ak,i=Bk,i=0
初始 B 矩阵所有位置为 0,每次可以选择若干个位置,将它们同时变成 1。要求做完操作后,矩阵 B 仍然是好的。设最多执行 k 次操作,则矩阵 A 的权值为 k。
小 █ 现在有一个 N×N 的 01
矩阵 M。由于 N 很大,所以 M 由特殊方式生成。
初始 M 中所有位置均为 0,有 Q 次修改操作。每次操作给定 x1,x2,y1,y2,对于满足 x1≤i≤x2 且 y1≤j≤y2 的所有位置 (i,j),将 Mi,j 变为 1−Mi,j。
定义 Si,j 为 M 前 i 行前 j 列构成的子矩阵的权值。
输入格式
第一行三个数 N,Q,op。
接下来 Q 行,每行四个数 x1,x2,y1,y2。
输出格式
若 op=0,输出一个数 SN,N。
若 op=1,输出一行 N 个数,分别是 SN,1,SN,2,⋯,SN,N。
输入输出样例
样例输入 1
2 2 1 1 1 1 1 2 2 2 2
样例输出 1
2 1
样例 2 & 3
详见下发文件。
数据范围
Subtask 编号 | 分值 | N≤ | 特殊性质 |
---|---|---|---|
1 | 5 | 4 | A |
2 | 10 | 50 | |
3 | 10 | 5000 | |
4 | 10 | 无 | |
5 | 15 | 2×105 | B |
6 | 15 | A | |
7 | 35 | 无 |
- 特殊性质 A:保证 op=0。
- 特殊性质 B:一次操作的代价为 (x2−x1+1)×(y2−y1+1),所有操作的代价之和 ≤2×106。
对于所有数据,保证: 1≤N,Q≤2×105,1≤x1≤x2≤N,1≤y1≤y2≤N,op∈{0,1}