Задача №2789. Своппер
Современные компьютеры зацикливаются в десятки раз эффективнее человека
Рекламный проспект OS Vista-N
Перед возвращением в штаб-квартиру корпорации Аазу и Скиву пришлось заполнить на местной таможне декларацию о доходах за время визита. Получилась довольно внушительная последовательность чисел. Обработка этой последовательности заняла весьма долгое время.
— Своппер кривой, — со знанием дела сказал таможенник.
— А что такое своппер? — спросил любопытный Скив.
Ааз объяснил, что своппер — это структура данных, которая умеет делать следующее.
- Взять отрезок чётной длины от \(x\) до \(y\) и поменять местами число \(x\) с \(x+1\), \(x+2\) с \(x+3\), и т.д.
- Посчитать сумму чисел на произвольном отрезке от \(a\) до \(b\).
Учитывая, что обсчёт может затянуться надолго, корпорация «МИФ» попросила Вас решить проблему со своппером и промоделировать ЭТО эффективно.
Во входном файле заданы один или несколько тестов.
В первой строке каждого теста
записаны число \(N\) — длина последовательности и число \(M\) — число
операций (\(1 \le N, \, M \le 100\,000\)).
Во второй строке теста содержится \(N\) целых чисел,
не превосходящих \(10^6\) по модулю — сама последовательность.
Далее следуют \(M\) строк — запросы в формате 1 \(x_i\) \(y_i\) — запрос
первого типа, и 2 \(a_i\) \(b_i\) — запрос второго типа.
Сумма всех \(N\) и \(M\) по всему файлу не превосходит \(200\,000\).
Файл завершается строкой из двух нулей. Гарантируется, что \(x_i \le y_i\), а
\(a_i \le b_i\).
Для каждого теста выведите ответы на запросы второго типа, как показано в примере. Разделяйте ответы на тесты пустой строкой.
5 5 1 2 3 4 5 1 2 5 2 2 4 1 1 4 2 1 3 2 4 4 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 Swapper 2: 10 9 2