#PQJ1808x9465. QOJ 1808_9465

    ID: 2708 传统题 4000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测差分区间DP

QOJ 1808_9465

标题: 基础 01 练习题 - Problem - QOJ.ac

#9465. 基础 01 练习题

Statistics

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

  1. 对于第 i(1≤i≤n) 行,不存在 1≤j,k≤m,j≠k 同时满足:

    Ai,j=Bi,k=1,Ai,k=Bi,j=0

  2. 对于第 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}