Problem link:
[contest][1]
[practice][2]
Difficulty :
Hard
Pre-requisites :
Balanced Binary Search Trees such as Treaps.
Problem:
You are given an array of size N. You need to answer M queries. Each query has one of the two types:
- 1 l r - Calculate some interesting function F for subarray indexed from l to r inclusive.
- 2 l r - Modify the given array by removing all elements having indices in range from l to r and then putting these numbers at the beginning of array. Order of all other elements remains same.
Definition of F can be found in the problem.
Explanation
We will use treap to solve this beautifull problem. First Let us see the values stored at a node.
- Val : To keep the value of the node.
- Cnt : To count the number of nodes in the tree.
- Prior : To keep the priority of node [ which is a part of treap data structure ]
- Lval : To keep the value of the leftmost node of the tree.
- Rval : To keep the value of the rightmost node of the tree.
- Ans : To Calculate the answer for the tree.
- Ltree : Keeps a pointer to the left subtree.
- Rtree : Keeps a pointer to the right subtree.
Let us call pointer to this structure as Tree structure.
The only challenge left in this problem is how to update the data in split and merge operations.
Let us first assume that we are able to do so and procede to give our algorithm keeping this as blackbox. We will make a visit again to it :).
Report Operation:
Split the root in to 3 trees t1,t2 and t3 such that t1 contains node from 1 to l-1 , t2 contains node from l to r, and t3 contains node from r+1 to N. Finally after you answer the query from the tree t2, we return our answer and merge the trees back.
//Aim is to return the value of the function from l to r.
Tree t1, t2, t3; //declare 3 trees
split(root, t1, t3, r); //Split the trees in to t1 and t3 , t1 has size r and t3 has size N-r.
split(t1, t1, t2, l - 1); //Split the trees so that [l,r] is in t2.
int ret = t2->ans;
//merge the trees back.
merge(t1, t1, t2);
merge(root, t1, t3);
return ret;
Another method for Reporting : Find the prefix sum for the treap upto r and prefix sum upto l and the difference is the answer. You can calculate prefix sum in the following manner :
int TreeNode::QuerySum(int rank)
if (this == null) return 0;
if (rank <= Ltree->size) return Ltree->QuerySum(rank);
return Ltree->ans + diff + Rtree->QuerySum(rank - lch->size - 1);
Update Operation:
We will split the tree into 3 parts t1,t2 and t3 such that t1 contains node from 1 to l-1 , t2 contains node from l to r, and t3 contains node from r+1 to N. When we merge the trees , we will merge t2 and t1 and then this will be merged with t3. [ Swapping the trees t1 and t2 which was needed ]
Tree t1, t2, t3;
split(root, t1, t3, r);
split(t1, t1, t2, l - 1);
merge(t1, t2, t1);
merge(root, t1, t3);
Now it’s high time to introduce the split and the merge functions.
Split Tree Operation:
Find the number of nodes in the left subtree[let us call it cur_add]. If cur_add is greater than or equal to Key then we split the left subtree otherwise we split the right subtree.
void split(Tree t, Tree &l, Tree &r, int key, int add = 0)
if (!t)
l = r = NULL;
return;
int cur_add = add + get_cnt(t->l);
if (cur_add >= key) split(t->Ltree, l, t->Ltree, key, add), r = t;
else split(t->Rtree, t->Rtree, r, key, add + get_cnt(t->Ltree) + 1), l = t;
//To Update the structure
upd_cnt(l);
upd_cnt(r);
Merge Tree Operation:
If the priority of the left subtree is more than the priority of the right subtree then the root of the tree will be choosen from the left subtree.
void merge(Tree &t, Tree l, Tree r)
//Update the structure
upd_cnt(l);
upd_cnt(r);
if (!l || !r)
t = l ? l : r;
return;
if (l->prior > r->prior) merge(l->Rtree, l->Rtree, r), t = l;
else merge(r->LTree, l, r->Ltree), t = r;
upd_cnt(t);
Updating the Count and the Answer
void upd_cnt(pTree v)
if (!v) return;
v->cnt = 1 + get_cnt(v->Ltree) + get_cnt(v->Rtree);
if (v->Ltree)
v->lval = v->Ltree->lval;
else
v->lval = v->val;
if (v->Rtree)
v->rval = v->Rtree->rval;
else
v->rval = v->val;
v->ans = 1 + get_ans(v->Ltree) + get_ans(v->Rtree);
if (v->Ltree && v->Ltree->rval == v->val) v->ans -= 1;
if (v->Rtree && v->Rtree->lval == v->val) v->ans -= 1;
Another Approach
You can use O(N * sqrt(N) ) decomposition to solve this problem. Make sqrt(N) chuncks of size sqrt(N) each and keep the Function value for each sqrt(N) chunck.
For Update operation, you will break atmost 2 sqrt chuncks, so you will create atmost 2 new chunks , so after sqrt(N) queries , rebuild the data structure.
When we update we also update the function value of the four chunks which are splitted in O(sqrt(N)) time.
Moving blocks can be done using brute forces in O(sqrt(N)) time.
For a Query, Iterate over all sqrt(N) blocks and add the answer for each block except the corner ones [ you need to take care for last and the first elements of the blocks ]. For first and last block , you can brute to find the answer in O(sqrt(N)) time.
Overall time complexity : sqrt(N) times rebuilding + sqrt(N) per query + O(N) initialization. Thus a total of O(N * sqrt(N)) time complexity.
Some Interesting Readings
[Treap Implementation][5]
Setter and Tester Solutions:
[setter][3]
[tester][4]
[1]: http://www.codechef.com/LTIME16/problems/CHEFC
[2]: http://www.codechef.com/problems/CHEFC
[3]: http://www.codechef.com/download/Solutions/LTIME16/Setter/CHEFC.cpp
[4]: http://www.codechef.com/download/Solutions/LTIME16/Tester/CHEFC.cpp
[5]: Treapuri
