CF2185F BattleCows

农夫 John 要派一头奶牛去参加国际牛类奥林匹克竞赛，但他太懒得给比赛出题，于是选择了另一种看似合理的方式：举办一场搏斗锦标赛！ 农夫 John 有 $2^n$ 头奶牛排成一排，第 $i$ 头奶牛的技能值为 $a_i$。每头奶牛一开始都在只包含自己的堆中，堆的技能值等于其中所有奶牛技能值的异或和$^{\text{∗}}$。例如，如果某个堆从下到上依次为第 $1, 3, 9$ 号奶牛，则该堆的技能值为 $1 \oplus 3 \oplus 9 = 11$。 以下过程会反复进行，直到只剩下一个堆为止： - 所有奇数位置（第 $1$ 个、第 $3$ 个等）的堆会与其右侧的堆进行对决。例如，第 $1$ 个堆会与第 $2$ 个堆对决，第 $3$ 个堆会与第 $4$ 个堆对决，依此类推。 - 技能值更高的堆获胜；若技能值相等，则编号较小的左边堆获胜。 - 获胜的堆会跳到失败的堆顶部，并且所有堆会依次向左移动，使得中间没有空挡。 为了让比赛更加精彩，农夫 John 准备了 $q$ 瓶魔药，第 $i$ 瓶魔药会将喝下它的奶牛的技能值设为 $c_i$。农夫 John 想在奶牛身上测试他的魔药，因此他让第 $i$ 瓶药被编号为 $b_i$ 的奶牛喝下，并随后举办锦标赛。对于每次试验，农夫 John 想知道喝下魔药的那头奶牛，在最终的堆中上方有多少头奶牛。 农夫 John 的魔药效果消散得很快，因此比赛结束时，喝下魔药的奶牛的技能值会恢复成原来的值。换句话说，所有询问都是独立的。 $^{\text{∗}}$ 一个数组 $x_1, x_2, \ldots, x_y$ 的异或和定义为 $x_1 \oplus x_2 \oplus x_3 \ldots x_{y-1} \oplus x_y$，其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。

输入的第一行为一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。 每个测试用例的第一行为两个整数 $n$ 和 $q$（$1 \le n \le 18$，$1 \le q \le 2 \cdot 10^5$） —— 其中 $2^n$ 是锦标赛中的奶牛数量，$q$ 是魔药数量。 第二行包含 $2^n$ 个整数 $a_1, a_2, \ldots, a_{2^n}$（$1 \le a_i \le 2^{30}$）——表示每头奶牛的技能值。 接下来的 $q$ 行，每行包含两个整数 $b_i$ 和 $c_i$（$1 \le b_i \le 2^n$，$1 \le c_i \le 2^{30}$）——表示喝下魔药的奶牛编号和它的新技能值。 保证所有测试用例中 $\sum 2^n \le 2^{18} = 262144$，且 $\sum q \le 2 \cdot 10^5$。

对于每次试验，输出一个整数，表示锦标赛结束后，喝下魔药的奶牛在最终堆中上方有多少头奶牛。

以下是第一个测试用例第一轮的比赛过程，奶牛的技能值没有改变，对阵如下： - 奶牛 $1$ 与奶牛 $2$ 对决。由于奶牛 $2$ 的技能值高于奶牛 $1$，奶牛 $2$ 获胜，其堆为 $1, 2$，堆的技能值为 $3 \oplus 1 = 2$。 - 奶牛 $3$ 与奶牛 $4$ 对决。由于奶牛 $4$ 的技能值高于奶牛 $3$，奶牛 $4$ 获胜，其堆为 $3, 4$，堆的技能值为 $7 \oplus 5 = 2$。 - 剩下的两个堆对决。两个堆的技能值相等，则左边堆获胜，最终堆为 $3, 4, 1, 2$，堆的技能值为 $2 \oplus 2 = 0$。 由于魔药给了第 $1$ 号奶牛，答案为 $1$，因为上方有一头奶牛。可视化如下图所示：  对于第一个测试用例的第二轮，奶牛 $4$ 的技能值变为 $8$，对阵如下： - 奶牛 $1$ 与奶牛 $2$ 对决。仍然是奶牛 $2$ 获胜，堆为 $1, 2$，堆技能值为 $3 \oplus 1 = 2$。 - 奶牛 $3$ 与奶牛 $4$ 对决。奶牛 $4$ 的技能值高于奶牛 $3$，因此 $4$ 号奶牛获胜，堆为 $3, 4$，堆技能值为 $8 \oplus 5 = 13$。 - 剩下两个堆对决。第二个堆的技能值更高，最终堆为 $1, 2, 3, 4$，堆的技能值 $2 \oplus 13 = 15$。 由于魔药给了第 $4$ 号奶牛，答案为 $0$，因为上方没有奶牛。 由 ChatGPT 5 翻译