#P18351. Omniscient Artist
Omniscient Artist
Omniscient Artist
平面上有 个边平行于坐标轴的矩形。第 个矩形为半开区域
给定正整数 ,且 。请依次求出恰好被 个矩形覆盖的区域面积。
形式化地,对于整数坐标 ,令
$$C(x,y)=\sum_{i=1}^{n} [x_{1,i}\le x<x_{2,i}]\,[y_{1,i}\le y<y_{2,i}].$$对每个 ,求满足 的整数点 数量。由于矩形边界均为整数,这等于恰好被 个矩形覆盖的单位格面积。
矩形可以重合,重合的矩形仍分别计入覆盖次数。只统计指定的恰好覆盖次数,不统计至少覆盖这些次数的面积。
输入格式
第一行两个整数 。
接下来 行,每行四个整数,顺序为
数据范围:
- ;
- 为整数,;
- ;
- 。
输出格式
输出 行。
第 行输出恰好被 个矩形覆盖的区域面积。
样例输入 1
9 3
6 8 4 5
6 9 1 3
1 5 1 9
6 8 7 9
5 6 2 9
2 8 1 2
1 8 5 9
2 4 5 7
7 9 2 6
样例输出 1
4
0
0
样例输入 2
10 4
1 2 1 6
3 9 8 9
2 3 1 9
2 8 8 10
3 7 2 10
1 7 2 7
5 6 2 6
5 8 3 7
6 7 4 7
1 4 7 10
样例输出 2
7
0