CF1249B2 Books Exchange (hard version)

本题的简单版与困难版的唯一区别在于数据范围。 有 $n$ 个小朋友，每个人都在读一本独一无二的书。在每一天结束时，第 $i$ 个小朋友会把自己的书交给第 $p_i$ 个小朋友（如果 $i = p_i$，则他把书交给自己）。保证所有 $p_i$ 都是 $1$ 到 $n$ 的不同整数（即 $p$ 是一个排列）。序列 $p$ 在每天都保持不变。 例如，如果 $n=6$，$p=[4, 6, 1, 3, 5, 2]$，那么第一天结束时，第 $1$ 个小朋友的书会被第 $4$ 个小朋友拿到，第 $2$ 个小朋友的书会被第 $6$ 个小朋友拿到，依此类推。第二天结束时，第 $1$ 个小朋友的书会被第 $3$ 个小朋友拿到，第 $2$ 个小朋友的书会被第 $2$ 个小朋友拿到，依此类推。 你的任务是，对于每个 $i$（$1 \leq i \leq n$），求出第 $i$ 个小朋友的书第一次回到他自己手中的天数。 举个例子：$p = [5, 1, 2, 4, 3]$。第 $1$ 个小朋友的书会被依次传递给： - 第一天后，被第 $5$ 个小朋友拿到， - 第二天后，被第 $3$ 个小朋友拿到， - 第三天后，被第 $2$ 个小朋友拿到， - 第四天后，被第 $1$ 个小朋友拿到。 所以，经过四天，第一个小朋友的书会回到他自己手中。第四个小朋友的书会在一天后回到自己手中。 你需要回答 $q$ 个独立的询问。

输入的第一行包含一个整数 $q$（$1 \leq q \leq 1000$），表示询问的数量。接下来有 $q$ 个询问。 每个询问的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示该询问中的小朋友数量。第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \leq p_i \leq n$，所有 $p_i$ 互不相同，即 $p$ 是一个排列），其中 $p_i$ 表示第 $i$ 个小朋友的书会交给第 $p_i$ 个小朋友。 保证所有询问中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个询问，输出 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示在该询问中第 $i$ 个小朋友的书第一次回到他自己手中的天数。

由 ChatGPT 4.1 翻译