689. Своппер
Перед возвращением в
штаб-квартиру Аазу и Скиву пришлось заполнить на местной таможне декларацию о
доходах за время визита. Получилась довольно внушительная последовательность
чисел. Обработка этой последовательности заняла весьма долгое время.
– Своппер кривой, – со знанием
дела сказал таможенник.
– А что такое своппер? – спросил любопытный
Скив.
Ааз объяснил, что своппер – это
структура данных, которая умеет делать следующее:
·
взять отрезок чётной длины от x
до y и поменять местами число x с x
+ 1, x + 2 с x + 3, и т.д;
·
посчитать сумму на произвольном отрезке от a до b.
Учитывая, что обсчёт может
затянуться надолго, корпорация “МИФ” попросила Вас решить проблему со своппером
и промоделировать ЭТО эффективно.
Вход. Состоит
из одного или нескольких тестов. В первой строке каждого теста записаны длина
последовательности n и количество
операций m (1 ≤ n, m
≤ 100 000). Вторая строка теста содержит n целых чисел, не превосходящих 106 по модулю – сама
последовательность. Далее следует m
строк – запросы в формате 1 xi
yi – запрос первого типа,
и 2 ai bi – запрос второго типа.
Сумма всех n и m по всему файлу не превосходит 200 000. Входные данные завершаются
строкой из двух нулей. Гарантируется, что xi
< yi, ai ≤ bi.
Выход. Для каждого теста выведите ответы
на запросы второго типа, как показано в примере. Разделяйте ответы на тесты
пустой строкой.
Пример входа
5 5
1 2 3 4 5
1 2 5
2 2 4
1 1 4
2 1 3
2 4 4
0 0
Пример выхода
Swapper 1:
10
9
2
РЕШЕНИЕ
структуры данных – декартово дерево,
неявный ключ
Анализ алгоритма
Заведем два декартовых дерева с
неявным ключом. Изначально занесем в первое числа, стоящие на нечетных позициях
(индексация начинается с 1), а во второе – числа на четных позициях. Тогда
операция своппера (запроса первого типа) будет заключаться в вырезке двух
участков деревьев и взаимной их переклейки.
Например, пусть изначально массив
содержит 11 элементов. Поступает запрос первого типа с параметрами x = 4, y = 7. Меняем местами части деревьев, лежащие в интервале [4; 7]
включительно. В данном случае следует поменять местами (переклеить) интервалы (a5, a7) и (a4,
a6).
В каждой вершине будем также
поддерживать значение, равное сумме чисел в поддереве, для котороого эта
вершина является корнем. Это необходимо для эффективного нахождения суммы чисел
на отрезке.
Реализация алгоритма
Объявим структуру Item вершины дерева с неявным ключом.
Элементы входной последовательности хранятся в значениях Value. В переменной Summa
хранится сумма всех элементов последовательности в поддереве с корнем в текущей
вершине.
struct Item
{
int cnt,
Value, Priority;
long long Summa;
Item *l, *r;
Item() { }
Item (int
Value) : Priority((rand() << 16u) + unsigned(rand())),
Value(Value),
Summa(Value), l(NULL), r(NULL) { }
};
Объявим указатель Pitem
на вершину дерева. Объявим два декартовых дерева T1 и T2.
typedef Item* Pitem;
Pitem T1, T2;
Функция cnt возвращает количество вершин в поддереве с
корнем t.
int cnt(Pitem t)
{
return t ?
t->cnt : 0;
}
Функция GetSum возвращает сумму элементов
последовательности, хранящуюся в вершинах поддерева с корнем t.
long long
GetSum(Pitem t)
{
return t ?
t->Summa : 0;
}
Функция пересчета данных в вершине t. Следует обновить количество вершин t → cnt в поддереве
t и сумму t → Summa.
void upd(Pitem t)
{
if (t)
{
t->cnt = 1 + cnt(t->l) + cnt
(t->r);
t->Summa = t->Value + GetSum(t->l)
+ GetSum(t->r);
}
}
Слияние двух деревьев l
и r в t.
void Merge(Pitem l, Pitem r, Pitem
&t)
{
if (!l || !r)
t = l
? l : r;
else if (l->Priority > r->Priority)
Merge(l->r, r, l->r), t = l;
else
Merge(l, r->l, r->l), t = r;
upd(t);
}
Разбиваем дерево t
по неявному ключу pos в l и r.
В левое дерево заносится в точности pos
вершин.
void Split(Pitem t, Pitem &l, Pitem
&r, int pos)
{
if (!t) return void( l = r =
0 );
if (pos <=
cnt(t->l))
Split(t->l, l, t->l, pos), r = t;
else
Split(t->r, t->r, r, pos - 1 -
cnt(t->l)), l = t;
upd(t);
}
Вычисляем суммы элементов последовательности aL + … + aR. Ищем соответствующие индексы суммируемых элементов в
деревьях T1 и T2. Для T1 это будет интервал [L1, R1], а для T2 интервал [L2, R2].
Вырежем поддеревья с ключами [L1,
R1] и [L2, R2], вычислим суммы элементов последовательности в них в
переменной res, после чего склеим
деревья обратно.
long long
Sum(int L, int
R)
{
if (L > R)
return 0;
int L1 = (L +
1) / 2, R1 = R / 2;
int L2 = L /
2, R2 = (R + 1) / 2 - 1;
Pitem A1, B1, C1, A2, B2, C2;
Split(T1,A1,B1,L1);
Split(B1,B1,C1,R1 - L1 + 1); // T1 = (A1, B1, C1)
Split(T2,A2,B2,L2);
Split(B2,B2,C2,R2 - L2 + 1); // T2 = (A2, B2, C2)
long long res = GetSum(B1) + GetSum(B2);
Merge(A1,B1,B1); Merge(B1,C1,T1);
Merge(A2,B2,B2); Merge(B2,C2,T2);
return res;
}
Реализация операции своппера на отрезке [L; R]
четной длины. Вырезаем соответствующие интервалы [L1, R1]
и [L2, R2] из деревьев T1
и T2 и меняем их местами.
void Swap(int
L, int R)
{
int L1 = (L +
1) / 2, R1 = R / 2;
int L2 = L /
2, R2 = (R + 1) / 2 - 1;
Pitem A1, B1, C1, A2, B2, C2;
Split(T1,A1,B1,L1);
Split(B1,B1,C1,R1 - L1 + 1); // T1 = (A1, B1, C1)
Split(T2,A2,B2,L2);
Split(B2,B2,C2,R2 - L2 + 1); // T2 = (A2, B2, C2)
Merge(A1,B2,B2);
Merge(B2,C1,T1); //
T1 = (A1, B2, C1)
Merge(A2,B1,B1);
Merge(B1,C2,T2); //
T2 = (A2, B1, C2)
}
Основная часть программы. Читаем входные данные. Строим
декартовы деревья T1 и T2.
while(scanf("%d
%d",&n,&m) , n + m)
{
T1 = T2 = NULL;
if (cs != 1)
printf("\n");
printf("Swapper
%d:\n",cs++);
for(i = 1; i
<= n; i++)
{
scanf("%d",&val);
if(i&1)
Merge(T1, new Item(val), T1);
else
Merge(T2, new Item(val), T2);
}
Последовательно обрабатываем запросы.
for(i = 0; i
< m; i++)
{
scanf("%d
%d %d",&type,&a,&b);
a--; b--;
if (type ==
1)
Swap(a,b);
else
printf("%lld\n",Sum(a,b));
}
}