A83458.地毯覆盖
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
有一块 N×N 的地板,行列均从 1 编号到 N。
接下来铺设 M 张“地毯”,第 i 张地毯给出一个矩形区域的两个角点坐标 (x1,y1) 与 (x2,y2)(均为闭区间、包含边界),表示把该矩形范围内的所有格子都再覆盖一层。
请你输出最终每个格子被覆盖了多少次。
输入格式
第一行:两个整数 N,M。
接下来 M 行:每行四个整数 x1,y1,x2,y2,表示在矩形 [x1,x2]×[y1,y2] 上覆盖一次。保证 1≤x1≤x2≤N 且 1≤y1≤y2≤N。
输出格式
输出 N 行,每行 N 个整数,用空格分隔,表示对应格子的被覆盖次数。
输入输出样例
输入#1
3 4 1 1 2 2 2 2 3 3 1 3 1 3 3 1 3 2
输出#1
1 1 1 1 2 1 1 2 1
说明/提示
-
1≤N≤2000
-
0≤M≤2×105
第 1 张:覆盖 (1,1)∼(2,2),这是一块 2×2 的矩形。
第 2 张:覆盖 (2,2)∼(3,3)。
第 3 张:只覆盖第 1 行第 3 列(一个点)。
第 4 张:覆盖第 3 行第 1~2 列。
叠加统计后得到上面的 3×3 结果。