← 返回题目列表

AtCoder · abc434_d

G. 云

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

天空由 2000 \times 2000 网格。
当抬头仰望天空时,位于 r从顶部数第行和 c从左边算起的第列称为 (r,c).

目前有云 1,2,\dots,N 漂浮在这片天空中。
细胞 (r,c) 被云层覆盖 i 当且仅当满足 U_i \le r \le D_i 和 L_i \le c \le R_i.

对于 k=1,2,\dots,N,回答以下问题:

  • 仅删除云 k 来自 N 云。此时,有 N-1 云彩在天空中漂浮。有多少细胞没有被云覆盖?

约束

  • 1 \le N \le 2 \times 10^5
  • 1 \le U_i \le D_i \le 2000
  • 1 \le L_i \le R_i \le 2000
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
U_1 D_1 L_1 R_1
U_2 D_2 L_2 R_2
\vdots
U_N D_N L_N R_N

输出

输出 N 行。
的 树的 i- 第行应包含问题的答案 k=i.


示例输入 1

5
2 4 1 4
3 3 3 5
1 3 4 6
4 5 3 5
5 5 4 6

示例输出 1

3999983
3999976
3999982
3999978
3999977

该图显示左上角 5 \times 6 天空区域。

  • 时云 1 被删除,被一些云覆盖的单元格数量是 17,因此未被任何云覆盖的单元格数量为 3999983.
  • 时云 2 被删除,被一些云覆盖的单元格数量是 24,因此未被任何云覆盖的单元格数量为 3999976.
  • 时云 3 被删除,被一些云覆盖的单元格数量是 18,因此未被任何云覆盖的单元格数量为 3999982.
  • 时云 4 被删除,被一些云覆盖的单元格数量是 22,因此未被任何云覆盖的单元格数量为 3999978.
  • 时云 5 被删除,被一些云覆盖的单元格数量是 23,因此未被任何云覆盖的单元格数量为 3999977.