{"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$ 的区间为 $[2, 2], [2, 3], [1, 3]$：\n\n- $k = 1$ 时：一个可行方案为 $[C]$，答案为 $1$；\n- $k = 2$ 时：一个可行方案为 $[C, B]$，答案为 $2$；\n- $k = 3$ 时：一个可行方案为 $[C, A, B]$，答案为 $3$；\n\n## Input\n\n第一行 $2$ 个整数 $n, m$ 代表座位和小朋友的数量。\n\n接下来 $m$ 行，每行 $2$ 个整数 $l[i], r[i]$ 代表第 $i$ 个小朋友的意愿区间。\n\n## Output\n\n输出 $n$ 行，第 $k$ 行代表只保留前 $1 \\sim k$ 个座位之后最多可以给几个小朋友安排座位。\n\n[samples]\n\n## Note\n\n### 样例 3-7\n\n见附件。\n\n### 数据范围\n\n对于所有数据，$1 \\leq n, m \\leq 2 \\times 10^5, 1 \\leq l[i] \\leq r[i] \\leq n$。\n\n本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。\n\n| 子任务编号 | 分值 | 数据范围 | 特殊性质 | 子任务依赖 |\n|:------------:|:------:|:----------:|:----------:|:------------:|\n| 1          | 26   | $n, m \\leq 10$ |          |            |\n| 2          | 28   | $n, m \\leq 100$ |          | 1          |\n| 3          | 11   | $n, m \\leq 5000$ | $l[i] = r[i]$ |            |\n| 4          | 26   | $n, m \\leq 5000$ |          | 1,2,3      |\n| 5          | 9    | $n, m \\leq 2 \\times 10^5$ |          | 1,2,3,4    |","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4160","tags":["贪心","线段树","并查集","单调队列","2024","北京","BCSP-X"],"sample_group":[["3 3\n2 2\n2 3\n1 3","1\n2\n3"],["8 9\n5 7\n6 7\n5 6\n6 7\n7 7\n5 7\n4 6\n1 1\n7 7","1\n1\n1\n2\n3\n4\n5\n5"]],"created_at":"2026-03-03 11:09:25"}}