English · Original
Chinese · Translation
Formal · Original
There are times you recall a good old friend and everything you've come through together. Luckily there are social networks — they store all your message history making it easy to know what you argued over 10 years ago.
More formal, your message history is a sequence of messages ordered by time sent numbered from 1 to _n_ where _n_ is the total number of messages in the chat.
Each message might contain a link to an earlier message which it is a reply to. When opening a message _x_ or getting a link to it, the dialogue is shown in such a way that _k_ previous messages, message _x_ and _k_ next messages are visible (with respect to message _x_). In case there are less than _k_ messages somewhere, they are yet all shown.
Digging deep into your message history, you always read all visible messages and then go by the link in the current message _x_ (if there is one) and continue reading in the same manner.
Determine the number of messages you'll read if your start from message number _t_ for all _t_ from 1 to _n_. Calculate these numbers independently. If you start with message _x_, the initial configuration is _x_ itself, _k_ previous and _k_ next messages. Messages read multiple times are considered as one.
## Input
The first line contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 105, 0 ≤ _k_ ≤ _n_) — the total amount of messages and the number of previous and next messages visible.
The second line features a sequence of integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ < _i_), where _a__i_ denotes the _i_\-th message link destination or zero, if there's no link from _i_. All messages are listed in chronological order. It's guaranteed that the link from message _x_ goes to message with number strictly less than _x_.
## Output
Print _n_ integers with _i_\-th denoting the number of distinct messages you can read starting from message _i_ and traversing the links while possible.
[samples]
## Note
Consider _i_ = 6 in sample case one. You will read message 6, then 2, then 1 and then there will be no link to go.
In the second sample case _i_ = 6 gives you messages 5, 6, 7 since _k_ = 1, then 4, 5, 6, then 2, 3, 4 and then the link sequence breaks. The number of distinct messages here is equal to 6.
有时你会想起一位老朋友，以及你们共同经历的一切。幸运的是，有社交网络——它们保存了你所有的消息历史，让你轻松知道十年前你争论过什么。
更正式地，你的消息历史是一个按发送时间排序的消息序列，编号从 #cf_span[1] 到 #cf_span[n]，其中 #cf_span[n] 是聊天中的消息总数。
每条消息可能包含一个指向其回复的较早消息的链接。当打开消息 #cf_span[x] 或获取其链接时，对话会以如下方式显示：#cf_span[k] 条前导消息、消息 #cf_span[x] 以及 #cf_span[k] 条后续消息（相对于消息 #cf_span[x]）。如果某侧的消息少于 #cf_span[k] 条，则全部显示。
在深入查阅你的消息历史时，你总是阅读所有可见消息，然后沿着当前消息 #cf_span[x] 中的链接（如果有）继续阅读，方式相同。
请确定从消息 #cf_span[t] 开始时，你会阅读多少条消息，其中 #cf_span[t] 从 #cf_span[1] 到 #cf_span[n]。这些数字需独立计算。如果你从消息 #cf_span[x] 开始，初始配置为 #cf_span[x] 本身、#cf_span[k] 条前导消息和 #cf_span[k] 条后续消息。重复阅读的消息仅计为一次。
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105]，#cf_span[0 ≤ k ≤ n]）——消息总数和可见的前导与后续消息数量。
第二行包含一个整数序列 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai < i]），其中 #cf_span[ai] 表示第 #cf_span[i] 条消息的链接目标，若无链接则为零。所有消息按时间顺序列出。保证消息 #cf_span[x] 的链接指向编号严格小于 #cf_span[x] 的消息。
请输出 #cf_span[n] 个整数，第 #cf_span[i] 个整数表示从消息 #cf_span[i] 开始，沿链接不断遍历所能读取的**不同**消息数量。
考虑第一个样例中 #cf_span[i = 6] 的情况：你将阅读消息 #cf_span[6]，然后 #cf_span[2]，然后 #cf_span[1]，之后不再有链接可跳转。
在第二个样例中，当 #cf_span[i = 6] 且 #cf_span[k = 1] 时，你首先看到消息 #cf_span[5, 6, 7]，然后是 #cf_span[4, 5, 6]，接着是 #cf_span[2, 3, 4]，之后链接序列中断。此处不同消息的总数为 #cf_span[6]。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105]，#cf_span[0 ≤ k ≤ n]）——消息总数和可见的前导与后续消息数量。第二行包含一个整数序列 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai < i]），其中 #cf_span[ai] 表示第 #cf_span[i] 条消息的链接目标，若无链接则为零。所有消息按时间顺序列出。保证消息 #cf_span[x] 的链接指向编号严格小于 #cf_span[x] 的消息。
## Output
请输出 #cf_span[n] 个整数，第 #cf_span[i] 个整数表示从消息 #cf_span[i] 开始，沿链接不断遍历所能读取的**不同**消息数量。
[samples]
## Note
考虑第一个样例中 #cf_span[i = 6] 的情况：你将阅读消息 #cf_span[6]，然后 #cf_span[2]，然后 #cf_span[1]，之后不再有链接可跳转。在第二个样例中，当 #cf_span[i = 6] 且 #cf_span[k = 1] 时，你首先看到消息 #cf_span[5, 6, 7]，然后是 #cf_span[4, 5, 6]，接着是 #cf_span[2, 3, 4]，之后链接序列中断。此处不同消息的总数为 #cf_span[6]。
**Definitions**
Let $ n, k \in \mathbb{Z} $ with $ 1 \leq n \leq 10^5 $, $ 0 \leq k \leq n $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers where $ 0 \leq a_i < i $ for all $ i \in \{1, \dots, n\} $, representing the link destination of message $ i $ (0 means no link).
For each message $ t \in \{1, \dots, n\} $, define the **visible set** starting at $ t $ as:
$$
V(t) = \{ \max(1, t - k), \dots, \min(n, t + k) \}
$$
Define the **link graph** $ G = (V, E) $ where $ V = \{1, \dots, n\} $ and $ E = \{ (i, a_i) \mid a_i \neq 0 \} $, i.e., a directed edge from $ i $ to $ a_i $.
**Objective**
For each $ t \in \{1, \dots, n\} $, compute the size of the set of distinct messages read when:
1. Starting at message $ t $, add all messages in $ V(t) $ to the read set.
2. While the current message $ x $ has a link $ a_x \neq 0 $, move to $ a_x $, and add all messages in $ V(a_x) $ to the read set.
3. Stop when no further links exist.
Let $ R(t) \subseteq \{1, \dots, n\} $ be the set of all distinct messages read starting from $ t $.
Output $ |R(t)| $ for each $ t = 1, \dots, n $.
API Response (JSON)
{
"problem": {
"name": "B. Chat",
"description": {
"content": "There are times you recall a good old friend and everything you've come through together. Luckily there are social networks — they store all your message history making it easy to know what you argued",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF928B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There are times you recall a good old friend and everything you've come through together. Luckily there are social networks — they store all your message history making it easy to know what you argued...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "有时你会想起一位老朋友，以及你们共同经历的一切。幸运的是，有社交网络——它们保存了你所有的消息历史，让你轻松知道十年前你争论过什么。\n\n更正式地，你的消息历史是一个按发送时间排序的消息序列，编号从 #cf_span[1] 到 #cf_span[n]，其中 #cf_span[n] 是聊天中的消息总数。\n\n每条消息可能包含一个指向其回复的较早消息的链接。当打开消息 #cf_span[x] 或获取其链接...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^5 $, $ 0 \\leq k \\leq n $. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers where $ 0 \\leq a_i < i $ for all $ i \\in ...",
"is_translate": false,
"language": "Formal"
}
]
}