U425441 PKUSC2019 D1T1 强制在线

yzh 喜欢可爱的在线算法哦。同 [U424061](https://www.luogu.com.cn/problem/U424061)，但强制在线，并且时限增大。

有 $n$ 个村庄排成一排，每个村庄里有一个人。第 $i$ 个村庄里的人要去第 $p_i$ 个村庄，且 $p$ 是 $1 \sim n$ 的一个排列。他们出行方式是每次交换相邻两个村庄的人。 现在政府要建立 $m$ 个哨卡，第 $i$ 个哨卡建立在村庄 $q_i$ 与 $q_i + 1$ 之间，每次交换的时候，如果中间有一个哨卡，或者交换双方有一个人经过了一个哨卡，则需要花费 $1$ 的代价。 政府每年建设一个哨卡。人们好奇，对于前 $i$ 年建设的 $i$ 个哨卡，每个人都走到对应村庄的最小代价是多少呢？由于这个问题太难了，所以交给聪明的你去做啦。 由于 yzh 喜欢在线的算法，所以她想让你每年立马告诉她答案哦。

第一行两个整数 $n$ 和 $m$。 第二行 $n$ 个整数 $p_i$，为 $1 \sim n$ 的一个排列。 接下来 $m$ 行，一行一个整数 $q'_i$，你需要将其异或上去年的答案 $lastans$，得到 $q_i = q'_i \operatorname{xor} lastans$，这一年添加 $(q_i, q_i + 1)$ 之间的哨卡。保证 $q_i$ 互不重复。初始 $lastans=736520$。

共 $m$ 行，每行一个整数，第 $i$ 行，表示加入前 $i$ 个哨卡，每个人走到终点的最小代价。

解密后的输入： ```none 10 8 9 10 7 3 1 5 8 6 2 4 5 1 7 2 3 4 8 9 ``` 对于 $30\%$ 的数据，$n \leq 10$； 对于 $100\%$ 的数据，$n \leq 5 \times 10 ^5$，保证 $p$ 是 $1 \sim n$ 的排列，$q_i$ 互不重复。 答案可能很大。可能需要更快的 IO 方式。 [博客 & 题解。](https://www.cnblogs.com/XuYueming/p/18144269)