| Codeforces Round 1074 (Div. 4) |
|---|
| Закончено |
Фермер Джон отправляет корову участвовать в Международной Коровьей Олимпиаде, но ему слишком лень писать задачи для конкурса, поэтому он делает следующее самое разумное: организует турнир по борьбе!
У фермера Джона есть $$$2^n$$$ коров, стоящих в ряд, при этом $$$i$$$-я корова имеет уровень навыка $$$a_i$$$. Каждая корова начинает в стопке, содержащей только её саму, и уровень навыка стопки равен XOR-сумме$$$^{\text{∗}}$$$ уровней навыка всех коров в ней. Например, если стопка состоит из коров с уровнями навыка $$$1, 3, 9$$$ снизу вверх, то уровень навыка стопки равен $$$1 \oplus 3 \oplus 9 = 11$$$.
Следующий процесс повторяется до тех пор, пока не останется только одна стопка.
- Каждая стопка на нечётной позиции ($$$1$$$-я, $$$3$$$-я и т.д.) начинает бой со стопкой справа от неё. Например, $$$1$$$-я стопка будет сражаться с $$$2$$$-й стопкой, $$$3$$$-я стопка будет сражаться с $$$4$$$-й стопкой и т.д.
- Стопка с более высоким уровнем навыка выиграет матч, при равенстве выигрывает левая стопка.
- Выигравшая стопка перепрыгнет на верх проигравшей стопки и сдвинет себя так, чтобы не осталось пробелов от побеждённых стопок.
Чтобы сделать это более захватывающим, фермер Джон создал $$$q$$$ зелий, так что $$$i$$$-е зелье делает уровень навыка коровы, которая его выпьет, равным $$$c_i$$$. Фермер Джон хочет протестировать свои зелья на коровах, поэтому он даёт $$$i$$$-е зелье корове $$$b_i$$$, а затем проводит турнир. Для каждого испытания фермер Джон хочет знать, сколько коров находится выше коровы, которая получила зелье, в финальной стопке.
Зелья фермера Джона быстро теряют свою силу, поэтому, когда турнир заканчивается, корова, которая получила зелье, вернёт свой уровень навыка к тому, каким он был изначально. Другими словами, все запросы независимы.
$$$^{\text{∗}}$$$XOR-сумма массива $$$x_1, x_2, \ldots, x_y$$$ равна $$$x_1 \oplus x_2 \oplus x_3 \ldots x_{y-1} \oplus x_y$$$, где $$$\oplus$$$ обозначает побитовую операцию 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}$$$) — индекс коровы, которая получает зелье, и новый уровень навыка коровы.
Гарантируется, что сумма $$$2^n$$$ по всем наборам не превышает $$$2^{18} = 262144$$$, а сумма $$$q$$$ по всем наборам не превышает $$$2 \cdot 10^5$$$.
Для каждого испытания выведите, сколько коров находится выше коровы, которая получила зелье, в финальной стопке.
42 21 3 5 71 14 81 21 31 41 23 41 8 3 10 2 5 7 15 38 121 92 12 11 2 3 43 1
100150231
Для первого раунда первого примера уровни навыка коров не меняются, и матчи проходят следующим образом:
- Коровы $$$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$$$.
Визуализация раунда показана ниже.
Для второго раунда первого примера уровень навыка коровы $$$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$$$.
