DRANGE - Editorial

PROBLEM LINK:

Practice
Contest

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.

18 Likes

I didnt get … if we were to use an array of size N… then we could have used A instead… can v take D of size N ? :open_mouth:

is there a solution to it using BIT ?

2 Likes

brilliant idea!

cant it be done without D?

Hum, the tester solution is not for this problem though.

1 Like

I do not understand this:

This is so because between the end points, A is monotonically increasing or monotonically decreasing.

decreasing?

Corrected it, thanks :slight_smile:

1 Like

@tyrant - corrected the link. Thanks for pointing out :slight_smile:

I had tried a O(T(N+M)). But it timed out. Could you tell me that how other people’s solutions got accepted.

1 Like

@gaurav_saxena2000 what is doing this statement in your code?

z = z - 2*w*z;

@betlista its for skipping if statement if mode is 0 than z remains z and if mode is 1 z becomes -z

@gaurav_saxena! Same here. It has got a strict time-limits. Change long long to int, cin to scanfs. I did that and it worked.

Yes.

Sorry, no but you could solve it using range queries and lazy propagation.:slight_smile: