[蓝桥杯 2020 国 A] 奇偶覆盖

Luogu

IDLGP8734

Time1000ms

Memory128MB

DifficultyP5

2020线段树扫描线蓝桥杯国赛

在平面内有一些矩形，它们的两条边都平行于坐标轴。我们称一个点被某个矩形覆盖，是指这个点在矩形的内部或者边界上。请问，被奇数个矩形覆盖和被偶数 $(\geq 2)$ 个矩形覆盖的点的面积分别是多少? ## Input 输入的第一行包含一个整数 $n$，表示矩形的个数。接下来 $n$ 行描述这些矩形，其中第 $i$ 行包含四个整数 $l_{i}, b_{i}, r_{i}, t_{i}$，表示矩形的两个对角坐标分别为 $\left(l_{i}, b_{i}\right),\left(r_{i}, t_{i}\right)$ 。 ## Output 输出两行。第一行包含一个整数，表示被奇数个矩形覆盖的点的面积。第二行包含一个整数，表示被偶数 $(\geq 2)$ 个矩形覆盖的点的面积。 [samples] ## Note 对于 $20 \%$ 的评测用例, $1 \leq n \leq 10,0 \leq l_{i}<r_{i} \leq 100,0 \leq b_{i}<t_{i} \leq 100$ 。对于 $40 \%$ 的评测用例, $1 \leq n \leq 1000,0 \leq l_{i}<r_{i} \leq 100,0 \leq b_{i}<t_{i} \leq 100$ 。对于 $60 \%$ 的评测用例, $1 \leq n \leq 10000,0 \leq l_{i}<r_{i} \leq 1000,0 \leq b_{i}<t_{i} \leq 1000$ 。对于 $80 \%$ 的评测用例, $1 \leq n \leq 10^5,0 \leq l_{i}<r_{i} \leq 10^5,0 \leq b_{i}<t_{i} \leq 10^5$。对于所有评测用例, $1 \leq n \leq 10^5,0 \leq l_{i}<r_{i} \leq 10^{9}, 0 \leq b_{i}<t_{i} \leq 10^{9}$。蓝桥杯 2020 年国赛 A 组 I 题。

Samples

Input #1

Output #1

8
2

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2020 国 A] 奇偶覆盖",
    "description": {
      "content": "在平面内有一些矩形，它们的两条边都平行于坐标轴。 我们称一个点被某个矩形覆盖，是指这个点在矩形的内部或者边界上。 请问，被奇数个矩形覆盖和被偶数 $(\\geq 2)$ 个矩形覆盖的点的面积分别是多少?",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8734"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在平面内有一些矩形，它们的两条边都平行于坐标轴。\n\n我们称一个点被某个矩形覆盖，是指这个点在矩形的内部或者边界上。\n\n请问，被奇数个矩形覆盖和被偶数 $(\\geq 2)$ 个矩形覆盖的点的面积分别是多少?\n\n## Input\n\n输入的第一行包含一个整数 $n$，表示矩形的个数。\n\n接下来 $n$ 行描述这些矩形，其中第 $i$ 行包含四个整数 $l_{i}, b_{i}, r_{i}, t_{i}...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments