PROBLEM LINK:
Author: Devanshu Agarwal
Tester: Michael Nematollahi
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Medium - Hard
PREREQUISITES:
Persistent Data Structures
PROBLEM:
Chef has recently learned about the most amazing dish. The recipe for this dish lists two sequences A_1,A_2,…,A_N and B_1,B_2,…,B_N and Q tasks. Chef noticed that there are only three types of tasks:
Type 1 : Z \,, Y : Set B_Z=Y
Type 2 : L\,, R\,, X : For each i such that L \leq i \leq R , Set A_i\,=\,B_{X+i−L}
Type 3 : L \,,R : compute the sum A_L+A_{L+1}+…+A_R
You need to perform all the queries.
N,Q\, \leq \, 2*10^5
EXPLANATION:
This tutorial assumes that you know persistent data structures. If you don’t, take a look at this tutorial.
There’s a solution to this problem that uses persistent treap, but it will not be covered. This problem is easy to solve using such data structure, but the data structure itself is complicated. We will describe a segment tree solution.
The first thing we need to maintain a persistent segment tree to handle the updates of our array B. So in total for each update, we will have a separate segment tree with changes resulting from that update (persistence mechanism).
Solving the first type of queries is a piece of cake then. Let’s think how to handle the second kind? Let’s maintain a segment tree for array A. (Just a segment tree that handles summation).
If the queries were like L\,, R\,, X : For each i such that L \leq i \leq R , Set A_i\,=\,B_{i}, the problem would be easier. Because we would have 2 segment trees with the same skeleton (structure). Our mission would be copying a subtree of our latest segment tree of array B and place it on top of its analogous subtree (subtree that covers the same range)in the data structure of A and then update results of ascendants.
Handling that would be easy, once we reach the subtree’s root in A we make it point to the subtree root in the latest B segment tree. With lazy propagation, everything will run in O(log \, N) per query. The third query would be straight forward. Think about what to do when pushing information down to children in case of lazy propagation.
Now let’s think about how to solve our original problem.
Type 2 : L\,, R\,, X : For each i such that L \leq i \leq R , Set A_i\,=\,B_{X+i−L}
The main difficulty in our problem is that ranges are not analogous, and we are not dealing with similar subtrees anymore. We may be copying the content of a whole subtree from B and we need to distribute it among 3 or 4 smaller subtrees in A data structures.
Suppose we are copying a range from B tree to A we will come across at most log \, N nodes that cover the range we are copying to. It’s hard to do our lazy propagation in O(1). Each time we come across a node in A that falls entirely within the range we are copying to, we figure its intersection with the range and get the sum of its analogous interval in B (corresponding range we are copying from) through a normal query on persistent segment tree paying the price of log\,n, and write this info into the node and return. In each node we store the identifier of the B segment tree we are getting information from (since there are many) and the range we are getting information from. Each time we need to push this information down in the tree (for some update or query) we shrink the interval and fix the intervals of the children and for each one get the information from its analogous range from one of B segment trees.
Finding sums in a segment tree is straight forward.
Complexity: O(Q \, log^2N)
