TWOARR - Editorial

PROBLEM LINK:

Practice
Contest

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)

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution

TESTER’s solution

2 Likes

I used exactly same approach but most people seem to use treap method. Can someone please give an intuition on how to solve problem using persistent treap?

1 Like

I got the logic in 2-3 mins but before that I never read the question due to very less number of submissions :frowning:
In addition to that I started contest 30 mins late…

1 Like

Pretty late answer, but it’s a standard persistent treap use case.
An implicit treap acts as a dynamic array: 1) one array can be split into two at any position, and 2) two arrays can be joined into one. Adding persistence allows copying of any arbitrary subarray. Amazingly, every operation takes logarithmic time and the implementation is also simple compared to other BBSTs. A treap is indeed a very cool structure :smiley:
Details can be found on cp-algorithms.

I can’t see how persistence is helping aren’t two segment trees with lazy propagation enough?
Beacause we are updating values of the nodes in A intersecting with the range with the range sum in B ,which can also be done by normal segment trees.
Can someone make it clear?

i use Segment Tree and Lazy Propagation and Binary Indexed Tree but getting WA … don’t know why … can you help me
mycode

I have a slightly different answer.
Maintain a usual segment tree for A, and maintain a segment tree with vector<int,int> for B. Maintaina t_time counter for time Whenever there’s an update of the first type, push make_pair(t_time,update_val) onto the vector corresponding to the update-range nodes. Now do a standard lazy propagation on the segment tree of A, but along with the start and end of the range for an update, also store timestamp of update. Then during each lazy propagation, we can perform a binary search on the timestamps of the corresponding nodes, to retrieve the value.
The time complexity of this is slightly worse than the intended solution, but it still is \mathcal O(N \frac{\log ^3 N}{\log \log N}). Why? doesn’t it look like for each lazy propagation step we’ll be querying upto N timestamps each in upto \log N intervals? Yes, but there are at most N timestamps in total across these, and the worst case is the equal distribution which gives \frac{\log ^2 N}{\log \log N} per lazy update.
In fact this ran pretty smooth in code, well under 1 second. I think maybe with some better analysis its possible to prove the complexity it N \log ^2 N? Even if not, the constant factor seems pretty small since it ran pretty well.