Need some help with Splay Trees (SPOJ : QMAX3VN)

Revision en2, by 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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English pranet 2016-01-13 10:59:06 319 Tiny change: ' chain BST. And sinc' - (published)
en1 English pranet 2016-01-13 10:47:17 513 Initial revision (saved to drafts)