← 返回题目列表

Codeforces · 2185/F

F. 战牛

中文机器翻译题面 查看原题

农夫约翰要送一头牛去参加国际牛奥林匹克竞赛,但他懒得写比赛题目,所以他做了下一个最合理的事情:格斗锦标赛!

Farmer John 有 $$$2^n$$$ 头奶牛排成一排,其中第 $$$i$$$ 头奶牛的技能水平为 $$$a_i$$$。每头牛都从一个仅包含其自身的堆栈开始,堆栈的技能水平等于其中所有牛的技能水平的异或和$$$^{\text{*}}$$$。例如,如果堆栈从下到上由奶牛 $$$1, 3, 9$$$ 组成,则该堆栈的技能级别为 $$$1 \oplus 3 \oplus 9 = 11$$$。

重复以下过程,直到只剩下一个堆栈。

  • 处于奇数位置的每个堆栈($$$1$$$st、$$$3$$$rd 等)都会与其右侧的堆栈开始战斗。例如,$$$1$$$st 堆栈将与 $$$2$$$nd 堆栈战斗,$$$3$$$rd 堆栈将与 $$$4$$$th 堆栈战斗,等等。
  • 技能水平较高的堆栈将赢得比赛,如果平局,最左边的堆栈获胜。
  • 获胜的堆栈将跳到失败的堆栈之上并自行移动,这样失败的堆栈就不会留下任何间隙。

为了让这更令人兴奋,Farmer John 创建了 $$$q$$$ 药水,这样第 $$$i$$$ 药水将喝它的牛的技能水平设置为 $$$c_i$$$。农夫约翰想要在奶牛身上测试他的药水,因此他将第 $$$i$$$ 药水给奶牛 $$$b_i$$$,然后进行锦标赛。对于每次试验,农夫约翰都想知道有多少头牛比最后一堆中被给予药水的牛高。

农夫约翰的药水很快就会消失,所以当锦标赛结束时,获得药水的牛会 技能等级恢复到原来的水平。换句话说,所有查询都是独立的。

$$$^{\text{*}}$$$数组 $$$x_1, x_2, \ldots, x_y$$$ 的异或和等于 $$$x_1 \oplus x_2 \oplus x_3 \ldots x_{y-1} \oplus x_y$$$ 其中 $$$\oplus$$$ 表示按位异或运算。

输入

输入的第一行包含一个整数 $$$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}$$$) — 被给予药水的牛的索引和牛的新技能水平。

保证所有测试用例的 $$$2^n$$$ 总和不超过 $$$2^{18} = 262144$$$,并且所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每次试验,输出最后一行中被给予药水的牛上方有多少头牛。

示例

输入
复制

4
2 2
1 3 5 7
1 1
4 8
1 2
1 3
1 4
1 2
3 4
1 8 3 10 2 5 7 1
5 3
8 12
1 9
2 1
2 1
1 2 3 4
3 1

输出
复制

1
0
0
1
5
0
2
3
1

注意

第一个测试用例的第一轮,奶牛的技能水平没有变化,比赛如下:

  • 奶牛 $$$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$$$,因为奶牛 $$$1$$$ 上面有一头奶牛。

该回合的可视化如下所示。

对于第一个测试用例的第二轮,cow $$$4$$$ 的技能等级现在为 $$$8$$$,匹配情况如下:

  • 奶牛 $$$1$$$ 和 $$$2$$$ 打架。由于奶牛 $$$2$$$ 的技能等级高于奶牛 $$$1$$$ 的技能等级,因此奶牛 $$$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$$$,因为奶牛 $$$4$$$ 之上没有奶牛。