Need some help with Splay Trees (SPOJ : QMAX3VN)

Правка en2, от pranet, 2016-01-13 10:59:06

Statement

Is it possible to solve this question using splay trees (without using any sort of randomization)?

I have tried the following:-

  • Treaps (isolate range for query): TLE Code

  • Treaps (query by traversing BST): AC Code

  • Splay (isolate range for query): TLE Code

  • Splay (query by traversing BST): TLE Code (This one fails when all the updates are before the queries.The updates might lead to a straight chain BST even with splaying. And since the query by traversing BST never calls splay(), every query takes linear time)

Suggestions please. An AC code (Splay Tree only) would be really helpful.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский pranet 2016-01-13 10:59:06 319 Tiny change: ' chain BST. And sinc' - (published)
en1 Английский pranet 2016-01-13 10:47:17 513 Initial revision (saved to drafts)