My problem is: Given a sequence of integers (a_n): a_1, a_2, ..., a_n. We do Q queries, each of them (l, r) requires reverse elements from a_l to a_r.
For example, Given a sequence: 2, 3, 4, 5. The query (1, 3) changes the sequence into 4, 3, 2, 5.
After performing Q queries, the problem asks us to print out the modified sequence.
How to solve this problem, if n and Q are large integers (such as 10^5)?
I hear that the solution uses an approach of Splay Tree.
Please help me and thank you.
Auto comment: topic has been updated by thanhnhan.gl (previous revision, new revision, compare).
Auto comment: topic has been updated by thanhnhan.gl (previous revision, new revision, compare).
//First of all, you need to know how to use a splay tree to solve problems on an sequence.
just maintain the reverse tag when you splay.
Hello,i don't now splay tree but this problem can be solved using treap (and i think any balanced binary search tree can do the job).
btw i explained here how the treap work and you can modify the code to solve this problem, soon i will post some explanation for how to solve the "reverse sub-array query" using treap, so now you can check the code here
First you need to implement the split and merge operations . Then you need to split the splay tree at the index l , Then again you have to split the right tree at index r-l . The left tree of this split operation holds the segment (l,r) . Now recursively swap the left and right pointers of the tree . After doing the swap operation we have reversed the tree . Now merge the three trees again . All these operation can be done in O(log(n)) amortized time .
Learn more about splay trees here : SplayTree