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.
