Блог пользователя amit.codename13

Algorithm for Robotic sort problem
Автор amit.codename13, 13 лет назад, По-английски
I am trying to solve this problem,

http://acm.uva.es/archive/nuevoportal/data/problem.php?p=3961

I can think of a O(n2) algorithm but its too slow for this problem. 
I think some data structure built with trees and linked list should solve this problem
Can anybody give some hints/ideas for this?
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
I know how to solve this problem with Cartesian tree. It allows you to reverse any segment in O(log2n).
Idea is like in RMQ with group operations.
To do this, you need to store in each vertex additional bool rev - need we to reverse this subtree, or not.
When we try to modify or query some vertex, check this value and if it's true, swap two childs, and <look comment at bottom>
→ Ответить