DRANGE - Editorial






Difference Sequence, Coordinate compression


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.


Maintain a difference sequence of the array. Each query can be processed in
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)


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
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.


Can be found here.


Can be found here.


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.


Corrected it, thanks :slight_smile:

1 Like

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

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:

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;

is there a solution to it using BIT ?


brilliant idea!

@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.

cant it be done without D?