Решение задачи Ксюша и битовые операции с Codeforces

Без пояснения   Просмотров: 35


У начинающего программиста Ксюши есть последовательность a, состоящая из 2n неотрицательных целых чисел: a1, a2, ..., a2n. Сейчас Ксюша изучает битовые операции. Чтобы лучше понять как они работают, Ксюша решила подсчитать некоторое значение v по a.

А именно, значение v считается в несколько итераций. На первой итерации, Ксюша записывает новую последовательность a1 or a2, a3 or a4, ..., a2n - 1 or a2n, состоящую из 2n - 1 элементов. Другими словами, она записывает побитовое ИЛИ соседних элементов последовательности a. На второй итерации, Ксюша записывает побитовое исключающее ИЛИ соседних элементов полученной после первой итерации последовательности. На третьей итерации Ксюша записывает побитовое ИЛИ соседних элементов последовательности, полученной после второй итерации. И так далее операции побитовое исключающее ИЛИ и побитовое ИЛИ чередуются. В конце концов получится последовательность, состоящая из одного элемента, этот элемент и равен v.

Рассмотрим пример, пусть последовательность a = (1, 2, 3, 4). Тогда запишем все преобразования (1, 2, 3, 4)  →  (1 or 2 = 3, 3 or 4 = 7)  →  (3 xor 7 = 4), в итоге v = 4.

Вам задана изначальная последовательность Ксюши. Но посчитать значение v по заданной последовательности было бы слишком просто, поэтому Вам дополнительно заданы m запросов. Каждый запрос — это пара целых чисел p, b. Запрос p, b означает, что нужно выполнить присвоение ap = b. После каждого запроса, нужно вывести новое значение v посчитанное по новой последовательности a.

Код

#include <iostream>
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
using namespace std;

const int B = 17, N = 1 << B;
int t[N << 1];

int f(int x, int y, bool b) {
	return (b ? (x | y) : (x ^ y));
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int b, q; cin >> b >> q;
	int n = 1 << b;
	rep(i, 0, n) cin >> t[i + n];
	for (int i = n - 1, b = 1; i; --i) {
		t[i] = f(t[i << 1], t[i << 1|1], b);
		if ((i & (i - 1)) == 0) b ^= 1;
	}
	while (q--) {
		int p; cin >> p; --p;
		p += n; cin >> t[p];
		for (bool b = 1; p >>= 1; b ^= 1)
			t[p] = f(t[p << 1], t[p << 1|1], b);
		cout << t[1] << '\n';
	}
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться