1 Тема от Hack-Yer

  • Hack-Yer
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-12-14
  • Сообщений: 64

Тема: Swapper

Хочу решит эту задачу. Уже неделю парюсь mad . Кто может помочь ? Если можно скиньте код пожалуйста. smile

2 Ответ от cmd

  • cmd
  • Участник
  • Неактивен
  • Откуда: Волжский
  • Зарегистрирован: 2009-06-11
  • Сообщений: 35

Re: Swapper

Можно заюзать Декартово дерево http://e-maxx.ru/algo/treap :
Можно представить например все числа так: сначала идут те, которые на четных позициях, а затем те которые на нечетных позициях.
И при запросе на своп элементов на отрезке l..r, считать индексы нечетных чисел oddL, oddR и четных evenL, evenR, затем разбивать весь массив на часть prefix evenPositions(evenL, evenR) middle oddPositions(oddL, oddR) suffix и затем мерджить это в нужном порядке prefix oddPositions(oddL, oddR) middle evenPositions(evenL, evenR) suffix.
А сумму считать за два запроса, sum(oddL, oddR) + sum(evenL, evenR).