QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100
[+40]
Statistics

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

  1. 对于第 i(1in) 行,不存在 1j,km,jk 同时满足: Ai,j=Bi,k=1,Ai,k=Bi,j=0

  2. 对于第 i(1im) 列,不存在 1j,kn,jk 同时满足: Aj,i=Bj,i=1,Ak,i=Bk,i=0

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

小 █ 现在有一个 N×N01 矩阵 M。由于 N 很大,所以 M 由特殊方式生成。

初始 M 中所有位置均为 0,有 Q 次修改操作。每次操作给定 x1,x2,y1,y2,对于满足 x1ix2y1jy2 的所有位置 (i,j),将 Mi,j 变为 1Mi,j

定义 Si,jMi 行前 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:一次操作的代价为 (x2x1+1)×(y2y1+1),所有操作的代价之和 2×106

对于所有数据,保证: 1N,Q2×105,1x1x2N,1y1y2N,op{0,1}