4080. AND Раунды

Имеется циклический массив A, содержащий n чисел. Во время AND раунда каждый элемент массива A заменяется битовой операцией AND его самого, предыдущего и следующего элементов массива. Все операции производятся одновременно. Сможете ли Вы найти значения всех элементов массива A после выполнения k таких AND раундов?

Вход. Первая строка содержит количество тестов t. Далее следуют 2t строк, по 2 на один тест. Первая строка содержит два целых числа n (3 ≤ n ≤ 20000) и k (1 ≤ k ≤ 10⁹). Следующая строка содержит n целых чисел A_i (0 ≤ A_i ≤ 10⁹) – начальные значения массива A.  

Выход.  Вывести t строк, по одной для каждого теста. Для каждого теста вывести список из n целых чисел – содержимое массива A после выполнения k AND раундов.

Пример входа	Пример выхода
2 3 1 1 2 3 5 100 1 11 111 1111 11111	0 0 0 1 1 1 1 1

РЕШЕНИЕ

структуры данных – дерево отрезков

Анализ алгоритма

Пусть изначально число A_i в p-ом бите содержит 0. Тогда после первого раунда числа A_i-1 и A_i+1 в p-ом бите будут содержать 0 (индексы вычисляются по модулю n). После k-го раунда числа A_i-1, …, A_i-k и A_i+1, …, A_i+k в p-ом бите будут содержать 0.

Если в p-ом бите A_i изначально находится 0, то;

· в p-ом бите A_i ни на каком раунде не появится 1;

· через k ≥ n / 2 раундов все числа массива в p-ом бите будут содержать 0.

Лемма. Если k ≥ n / 2, то для решения задачи достаточно вычислить побитовый AND всех элементов массива и вывести его n раз. Что и будет ответом.

Лемма. Если k < n / 2, то на A_i после k раундов подействуют начальные значения A_i-1, …, A_i-k и A_i+1, …, A_i+k. Если одно из них в p-ом бите содержит 0, то после k раундов A_i в в p-ом бите будет также содержать 0. Значит для ответа на вопрос достаточно вычислить побитовый AND элементов A_i-k, …, A_i, …, A_i+k. Это можно совершить за время O(log₂n), если на элементах входного массива A построить дерево отрезков, поддерживающее операцию побитового AND.

Реализация алгоритма

Объявим входной массив а. Дерево отрезков храним в массиве SegTree.

#define MAX 20010

int a[MAX];

int SegTree[4*MAX];

Построение дерева отрезков, которое поддерживает битовую операцию AND.

void BuildTree(int *a, int Vertex, int Left, int Right)

{

if (Left == Right)

SegTree[Vertex] = a[Left];

else

{

int Middle = (Left + Right) / 2;

BuildTree(a, 2*Vertex, Left, Middle);

BuildTree(a, 2*Vertex+1, Middle+1, Right);

SegTree[Vertex] = SegTree[2*Vertex] & SegTree[2*Vertex+1];

}

}

Вершине Vertex соответствует отрезок [LeftPos, RightPos]. Функция Query возвращает значение a_Left & a_Left+1 & … & a_Right.

int Query(int Vertex, int LeftPos, int RightPos, int Left, int Right)

{

if (Left > Right) return -1;

if ((Left == LeftPos) && (Right == RightPos))

return SegTree[Vertex];

int Middle = (LeftPos + RightPos) / 2;

return Query(2*Vertex, LeftPos, Middle, Left, min(Right,Middle)) &

Query(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1),Right);

}

Основная часть программы. Читаем входные данные в массив а.

scanf("%d",&tests);

while(tests--)

{

scanf("%d %d",&n,&k);

for(i = 0; i < n; i++) scanf("%d",&a[i]);

Если количество раундов k не меньше половины количества элементов массива, то вычисляем AND всех элементов в переменной res.

if (k >= n / 2)

{

for(res = a[0], i = 1; i < n; i++) res &= a[i];

Выводим значение res n раз.

for(i = 0; i < n; i++)

{

if (i) printf(" ");

printf("%d",res);

}

printf("\n");

continue;

}

Для быстрого ответа на каждый тест построим дерево отрезков из элементов массива А.

BuildTree(a,1,0,n-1);

Вычисляем значение A_i после k раундов. Оно равно A_i-k & … & A_i &…& A_i+k. Индексы элементов вычисляются по модулю n. Если (i – k ) mod n < (i + k) mod n, то достаточно одного запроса на дереве отрезков. Иначе находим AND элементов от (i – k ) mod n до n – 1 и от 0 до (i + k) mod n.

for(i = 0; i < n; i++)

{

int Start = (i - k + n) % n;

int End = (i + k + n) % n;

if (Start < End) res = Query(1,0,n-1,Start,End);

else res = Query(1,0,n-1,Start,n-1) & Query(1,0,n-1,0, End);

if (i) printf(" ");

printf("%d",res);

}

printf("\n");

}