### PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

**Setter:** Teja Vardhan Reddy

**Tester:** Hasan

**Editorialist:** Taranpreet Singh

### DIFFICULTY:

Medium

### PREREQUISITES:

Time complexity analysis, Set data structure and non-trivial implementation skills. Merge sort Tree or binary search and value compression.

### PROBLEM:

Given two array A and B, define similarity of two arrays as number of positions i such that A* == B*. Perform Q range updates and print similarity of arrays after each update. Range update assign every element of A in range [L, R] to C. Queries are online. i.e. we have to answer queries in same order as input.

### SUPER QUICK EXPLANATION:

- Represent ranges of consecutive positions having same values and store them in a balanced binary search tree. Calculate initial similarity naively, and for every update, update the intervals for new values, updating similarity simultaneously.
- Utilize the fact that B doesn’t change, preprocess to answer queries of type - count Number of positions in range [L,R] such that B* == C.
- This solution works fast enough, as proved in Time complexity analysis part at the end.

### EXPLANATION:

This problem has a relatively simple solution if comparing with usual second hardest problem, but proving that the solution runs with time is not trivial, earning this problem spot of second hardest problem.

Time complexity of solution will be analysed at the end, so please have patience, when i make any assumption.

So, Solution for first sub-task is simple, perform updates naively, and calculate similarity every time, giving O(N^2) time complexity, too slow to pass final sub task.

First of all, Notice a fact that suppose we have similarity already calculated before ith query [L,R]. We can see, that similar positions change only in range of update, since at all other positions, both arrays remain unchanged. This way, If we can calculate the change in similarity cause due to current update within update range, we can calculate answer.

Let us represent the array A in a different format. Create tuple of type (l,r,c) representing that elements of A in range [l, r] have value c, and store it in a set, ordered by left end of range (right end will also work, with changes in implementation.

Now, From this point, dont worry about complexity till i mention myself.

Talking about updates first, Perform update in manner, suppose update range is [L, R]. Give a thought about how will A look like after update. Some ranges which coincide with update range, would be modified, and ranges lying completely inside update range would be deleted and one new range would be inserted. Got this much? Right. If not, re-read because next paragraph won’t make sense without this.

Now, updating answer. Suppose before update, we had x positions in update range which were similar to array B. Current answer gets reduced by x. Also suppose, that after update, y positions in update range are similar. Answer increases by y. So, After every update, Answer becomes Ans-x+y.

Let’s calculate y first. We know, after update, all elements in update range in array A will be c. So, y is same as Number of positions in array B within update range, which have value c. This problem is well known, and can be solved using binary search, Merge sort tree (though slower). This problem will be explained soon. Suppose we are using Merge sort tree.

So, now that we have calculated y, all that remains is to calculate x. Let us represent x as a summation in terms of ranges completely and partially covered in range. For every range (l,r,c) completely inside update range, we know all elements in range have value c. So, we query to Merge sort Tree, to tell us number of positions in range (l,r) in array B having value c. This is same as problem above.

But we need to handle boundary ranges carefully, make new range for each border.

Suppose we have array A initially 1 1 2 1 2. So, its represent is set {(0,1,1),(2,2,2), (3,3,1), (4,4,2)}. (zero-based indexing). Say update is [1,3] to 4 We Final array after update should look like {(0,0,1), (1,3,4), (4,4,2)}.

Another case to be handled carefully is when a range fully covers the update range itself. This all is implementation stuff, so, will depend more on how you handle cases. Refer setter solution for implementation.

But, we still need to solve sub-problem, Given a permanent array, count number of elements in range l to r, with value c. It can be solved using two methods, one faster, other slower but simpler. Binary search and Merge sort tree.

Binary search idea involve compressing the values in array first, make a sorted vector corresponding to each value in array which stores every position of value in B, and for every query (l,r,c), if there doesn’t exist vector for value c, there isn’t any position in B which have c as value. Otherwise we can see that number of elements in range l to r is same as number of values in range from start to r less number of elements in range start to l-1. This can be easily done using binary search, and gives O(logN) (or even faster, exactly, O(log(no of elements in vector)).

Using merge sort tree, we maintain a map on every segment (total N*logN maps it become). It is very simple to query, just like segment tree, as explained here and here too.

So, we have solved the problem. Implementation is messy, but worth a try. I know you all are shouting at me saying that this solution would be inefficient, rest assured, this time i have a proof to proudly claim that this is efficient enough, let’s discuss it.

### TIME COMPLEXITY ANALYSIS:

First of all, set, at any point, cannot have more than N ranges. That happens when no two consecutive values are same.

Second thing, Let us find maximum number of insertions possible. We see, that we can alter at most three ranges, (one for l to r), and two boundary conditions. This way, We can insert at max 3 ranges, resulting in maximum N+3*Q insertions, which is linear in respect of N+Q.

Finally, Total number of deletions can never be more than initial ranges plus inserted ranges, thus deletions also are of linear complexity.

Every insertion and deletion takes only O(LogN) time (binary search on B), so, this solution has overall complexity O((N+Q)*logN). Preprocessing on B takes O(NlogN) time only, and thus, is dominated by queries.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution

Tester’s solution

Until above links are not working, feel free to refer solution here.

EDIT: Found an interesting problem here.

Feel free to Share your approach, If it differs. Suggestions are always welcomed.