[BCSP-X 2024 12 月小学高年级组] 排座位

Luogu

IDLGB4160

Time1000ms

Memory512MB

DifficultyP4

贪心线段树并查集单调队列2024北京BCSP-X

有 $n$ 个座位，从左到右编号为 $1 \sim n$。现在有 $m$ 个小朋友，第 $i$ 个小朋友可以坐在 $l[i] \sim r[i]$ 这些座位上，每个座位至多坐一个人。现在请问，如果只保留 $1 \sim k$ 这些座位，最多可以给多少小朋友安排座位。请你输出 $k = 1 \sim n$ 的所有答案。例如 $n = 3, m = 3$，$3$ 个小朋友 $A, B, C$ 的区间为 $[2, 2], [2, 3], [1, 3]$： - $k = 1$ 时：一个可行方案为 $[C]$，答案为 $1$； - $k = 2$ 时：一个可行方案为 $[C, B]$，答案为 $2$； - $k = 3$ 时：一个可行方案为 $[C, A, B]$，答案为 $3$； ## Input 第一行 $2$ 个整数 $n, m$ 代表座位和小朋友的数量。接下来 $m$ 行，每行 $2$ 个整数 $l[i], r[i]$ 代表第 $i$ 个小朋友的意愿区间。 ## Output 输出 $n$ 行，第 $k$ 行代表只保留前 $1 \sim k$ 个座位之后最多可以给几个小朋友安排座位。 [samples] ## Note ### 样例 3-7 见附件。 ### 数据范围对于所有数据，$1 \leq n, m \leq 2 \times 10^5, 1 \leq l[i] \leq r[i] \leq n$。本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。 | 子任务编号 | 分值 | 数据范围 | 特殊性质 | 子任务依赖 | |:------------:|:------:|:----------:|:----------:|:------------:| | 1 | 26 | $n, m \leq 10$ | | | | 2 | 28 | $n, m \leq 100$ | | 1 | | 3 | 11 | $n, m \leq 5000$ | $l[i] = r[i]$ | | | 4 | 26 | $n, m \leq 5000$ | | 1,2,3 | | 5 | 9 | $n, m \leq 2 \times 10^5$ | | 1,2,3,4 |

Samples

Input #1

Output #1

1
2
3

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[BCSP-X 2024 12 月小学高年级组] 排座位",
    "description": {
      "content": "有 $n$ 个座位，从左到右编号为 $1 \\sim n$。现在有 $m$ 个小朋友，第 $i$ 个小朋友可以坐在 $l[i] \\sim r[i]$ 这些座位上，每个座位至多坐一个人。 现在请问，如果只保留 $1 \\sim k$ 这些座位，最多可以给多少小朋友安排座位。请你输出 $k = 1 \\sim n$ 的所有答案。 例如 $n = 3, m = 3$，$3$ 个小朋友 $A, B, C$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4160"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个座位，从左到右编号为 $1 \\sim n$。现在有 $m$ 个小朋友，第 $i$ 个小朋友可以坐在 $l[i] \\sim r[i]$ 这些座位上，每个座位至多坐一个人。\n\n现在请问，如果只保留 $1 \\sim k$ 这些座位，最多可以给多少小朋友安排座位。请你输出 $k = 1 \\sim n$ 的所有答案。\n\n例如 $n = 3, m = 3$，$3$ 个小朋友 $A, B, C$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments