P14980 [USACO26JAN1] COW Traversals G

农夫 John 的农场上有 $N$ 头（$1\le N\le 2\cdot 10^5$）奶牛，编号为 $1\dots N$，每头奶牛住在自己的牛棚里。每头奶牛 $i$ 都有一个最好的朋友 $a_i$（$1\le a_i\le N$）。奶牛可以与自己做最好的朋友，并且多头奶牛可以有相同的最好朋友。奶牛们喜欢聚会，因此它们决定连续举办 $M$（$1\le M\le 2\cdot 10^5$）个晚上的聚会。 在第 $i$ 个晚上，奶牛 $c_i$ 决定在自己的牛棚举办一场类型为 $t_i$ 的聚会，其中 $t_i\in \texttt{"COW"}$。这个聚会将在之后的所有晚上持续存在，直到奶牛 $c_i$ 决定举办一个不同类型的聚会为止。 每个晚上，每头奶牛都会试图去参加一个聚会。如果一头奶牛不是聚会的举办者，它会先查看它最好朋友的牛棚，如果那里没有聚会，它就会跟随它最好的朋友去它要去的地方（那头奶牛也可能跟随它最好的朋友，依此类推）。有可能一头奶牛永远找不到聚会，那么它当晚就会放弃。 计算每个晚上，最终分别参加类型为 $\texttt{C}$、$\texttt{O}$ 和 $\texttt{W}$ 的聚会的奶牛数量。

第一行包含 $N$，表示奶牛的数量。 第二行包含 $a_1,\dots, a_N$，其中 $a_i$ 是奶牛 $i$ 的最好的朋友。 第三行包含 $M$，表示晚上的数量。 接下来的 $M$ 行，每行包含一个整数 $c_i$（$1\le c_i\le N$）和一个字符 $v_i$，分别表示举办聚会的奶牛和聚会类型。

输出 $M$ 行，第 $i$ 行包含 $3$ 个空格分隔的整数，分别表示第 $i$ 个晚上参加类型为 $\texttt{C}$、$\texttt{O}$ 和 $\texttt{W}$ 的聚会的奶牛数量。

在第 $1$ 个晚上，只有牛棚 $2$ 有一个类型为 $\texttt{C}$ 的聚会，只有奶牛 $1$ 和 $2$ 参加。 在第 $2$ 个晚上，牛棚 $4$ 新增了一个类型为 $\texttt{C}$ 的聚会，奶牛 $3$、$4$ 和 $5$ 现在可以到达该聚会。 在第 $3$ 个晚上，牛棚 $4$ 的聚会类型变为 $\texttt{W}$，影响奶牛 $3$、$4$ 和 $5$。 在第 $4$ 个晚上，牛棚 $2$ 的聚会类型变为 $\texttt{O}$，影响奶牛 $1$ 和 $2$。 --- - 输入 $2$：$N, M \leq 100$ - 输入 $3$-$4$：$N, M \leq 4000$ - 输入 $5$-$9$：$\{a_i\}$ 是 $\{1,\dots, N\}$ 的一个排列 - 输入 $10$-$21$：无额外约束。 翻译由 DeepSeek V3 完成