Need help with understanding an interesting solution for Codechef SORTING

Правка en2, от grey_rabbit, 2020-01-27 18:38:07

Problem statement: SORTING

A common solution for this problem is to use Persistent Segment tree and Binary Search, which runs in O(n log n). However, as I was reading the editorial for some extra insights, I encountered a solution that doesn't involve any advanced data structure but a Doubly Linked List, and (according to the author of the solution) runs in O(n). I spent an hour examining the solution but still haven't managed to understand it thoroughly. So far, I've understood the two functions to create and delete elements from the linked list, but couldn't how T[b] and T[e] work. Can someone please help me out ?

Link to the solution

Теги #codechef, #segment tree, #quick sort

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский grey_rabbit 2020-01-27 18:38:07 13
en1 Английский grey_rabbit 2020-01-27 17:37:12 881 Initial revision (published)