4092 绒绒鸹

题面

内容

给一个长 $n$ 的序列，有 $m$ 次操作，每次操作会给你一个数 $x$，你需要在序列的 $x$ 位置放一只绒绒鸹，之后查询 $x$ 位置的绒绒鸹数。

每次操作结束后，绒绒鸹会变得很活泼，于是会开始蹦蹦跳跳，即对每个 $1$ 到 $n$ 之间的整数 $i$，$i$ 位置的所有绒绒鸹都会跳到 $a_i$ 位置。

输入

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行表示 $a_i$。

接下来一行一个整数 $m$

接下来 $m$ 行每行一个整数 $x$，表示在 $x$ 位置放置一只绒绒鸹。

本题强制在线，即对于输入的 $m$ 次操作的数，第 $i$ 次的数需要异或上第 $i-1$ 次操作的答案。

输出

输出 $m$ 行，第 $i$ 行输出一个整数，表示第 $i$ 次操作的答案。

样例1

输入

6
1
2
1
3
3
6
5
1
4
7
3
7

输出

1
1
1
1
2

提示

对于 $10\%$ 的数据，满足 $1\le n,m\le 7812$。

对于 $20\%$ 的数据，满足 $1\le n,m\le 15625$。

对于 $30\%$ 的数据，满足 $1\le n,m\le 31250$。

对于 $40\%$ 的数据，满足 $1\le n,m\le 62500$。

对于 $50\%$ 的数据，满足 $1\le n,m\le 125000$。

对于 $60\%$ 的数据，满足 $1\le n,m\le 250000$。

对于 $100\%$ 的数据，满足 $1\le n,m\le 5\times 10^5$，$1\le a_i\le n$。

思路

树链剖分：

dfs序可以保证对任何一个点的子树都是序列中的一段区间。

重儿子：子树大小最大的儿子

重链上每取一个区间都是在dfs序上一段连续的区间

往上跳一次轻边至少会翻倍

那么路径最多就可以通过$log$个区间连接起来

维护一下当前位置的i还要跳几步才会跳到重链头

用小根堆维护f的最小值，再开个全局标记。