#PQJ1808x9465. QOJ 1808_9465
QOJ 1808_9465
标题: 基础 01 练习题 - Problem - QOJ.ac
#9465. 基础 01 练习题
对于一个 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}