### PROBLEM LINK:

### DIFFICULTY:

Easy

### PREREQUISITES:

Difference Sequence, Coordinate compression

### PROBLEM:

You’re given an array of **N** integers. You’ve to process **M** types of queries where each

query asks you to add/ subtract a constant integer from a consecutive range of

the array. In the end, you’re to find out the minimum and maximum number of the array.

### QUICK EXPLANATION:

Maintain a difference sequence of the array. Each query can be processed in

**O(1)**

time. After that restore the whole sequence in **O(N)** time and find the minimum

and maximum. Total time taken per test case is **O(N+M)**

### DETAILED EXPLANATION:

Let **A** be the given array where initially **A[i] = i** for all **i**. Let’s

create another array **D** of length **N-1** where **D[i] = A[i+1] - A[i]**. Initially all

entries of **D** are 1. What happens to **D** when you add **z** to **A[x…y]** ?

**D[x-1]** increases by **z** and **D[y]** decreases by **z**. Besides these two entries, no

other entries of **D** change! This is convenient because we can update **D** in

**O(1)**

time by changing only these two entries. Now we have processed all queries and

made changes in **D**. How do we restore the original sequence again? Well if we can

keep track of **A(1)** and have all the entries of **D**, we can restore it.

```
D[1] = A[2] - A[1] Rearranging, we get
A[2] = A[1] + D[1] Similarly :
A[3] = A[2] + D[2]
.
.
.
A[N] = A[N-1] + D[N-1]
```

So we can restore the whole sequence of **A**. Once we do that, we can find min and

max values of **A** in **O(N)** time.

Time limit is a little strict for **O(T(N+M))** solutions. We indeed do have a

faster solution. This solution is **O(T * MlogM)** and is a slight variant of the

previous algorithm. In previous algorithm, we’re reconstructing the whole

sequence **A** and then seeing each entry if it is min or max. This part of the

solution takes **O(N)** time. The observation to make here is that minimum and maximum

would appear only near the end points of the segment on which a query acts. This

is so because between the end points, **A** is monotonically increasing. As there are **M** queries, so there are **O(M)** critical points

which could be checked. Look at tester’s solution for a clean implementation of

this method. Another way of writing **O(M logM)** solution would’ve been to use a

segment tree only on critical points.

### SETTER’S SOLUTION:

Can be found here.

### TESTER’S SOLUTION:

Can be found here.