[THUPC 2024 初赛] 套娃

Luogu

IDLGP9970

Time1000ms

Memory512MB

DifficultyP6

2024THUPC

我们定义一个集合的 $\operatorname{mex}$ 是最小的不在 $S$ 中的非负整数。给定一个序列 $a_1,\dots,a_n$，对于每个 $1\leq k\leq n$，我们按照如下方式定义 $b_k$： - 对于 $a$ 的所有长为 $k$ 的子区间，求出这个子区间构成的数集的 $\operatorname{mex}$。 - 对于求出的所有 $\operatorname{mex}$，求出这个数集自己的 $\operatorname{mex}$，记为 $b_k$。请你求出序列 $b$。 ## Input 第一行输入一个正整数 $n$（$1\leq n\leq 10^5$）。第二行输入 $n$ 个整数 $a_1,\dots,a_n$（$0\leq a_i\leq n$）。 ## Output 一行输出 $n$ 个整数 $b_1,\dots,b_n$。 [samples] ## Note ### 题目使用协议来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。以下『本仓库』皆指 THUPC2024 初赛官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)） 1. 任何单位或个人都可以免费使用或转载本仓库的题目； 2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限； 3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。

Samples

Input #1

6
0 0 0 1 2 3

Output #1

2 3 4 0 0 0

API Response (JSON)

{
  "problem": {
    "name": "[THUPC 2024 初赛] 套娃",
    "description": {
      "content": "我们定义一个集合的 $\\operatorname{mex}$ 是最小的不在 $S$ 中的非负整数。 给定一个序列 $a_1,\\dots,a_n$，对于每个 $1\\leq k\\leq n$，我们按照如下方式定义 $b_k$： - 对于 $a$ 的所有长为 $k$ 的子区间，求出这个子区间构成的数集的 $\\operatorname{mex}$。 - 对于求出的所有 $\\operatorname{m",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9970"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "我们定义一个集合的 $\\operatorname{mex}$ 是最小的不在 $S$ 中的非负整数。\n\n给定一个序列 $a_1,\\dots,a_n$，对于每个 $1\\leq k\\leq n$，我们按照如下方式定义 $b_k$：\n\n- 对于 $a$ 的所有长为 $k$ 的子区间，求出这个子区间构成的数集的 $\\operatorname{mex}$。\n- 对于求出的所有 $\\operatorname{m...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments