PROBLEM LINK:
[Problem][1]
[Contest][2]
Author: Keshav Aggarwal
Tester: keshav Aggarwal
Editorialist: Gagandeep Nagpal
DIFFICULTY:
Medium
PREREQUISITES:
sqrt decomposition, preprocessing
PROBLEM:
Given a sequence of N integers A1,A2,…,AN, where each Ai is between 1 to M, you are to answer Q queries of the following kind:
Given L and R, where 1≤L≤R≤N, what is the maximum |x−y| such that L≤x,y≤R and Ax=Ay?
Note that in the problem, Q is actually K.
QUICK EXPLANATION:
For each i, 1≤i≤N, precompute the following in O(N) time:
next[i], the smallest j > i such that Ai=Aj
prev[i], the largest j < i such that Ai=Aj
Let S=sqrt(N), and B=⌈N/S⌉. Decompose the array into B blocks, each of size S (except possibly the last). For each i, 1≤i≤N, and
0≤j≤B−1, precompute the following in O(N*sqrt(N)) time:
LastInBlock[ j ][ i ], the largest k≤ jS+S such that Ak=Ai blockAns[ j ][ i ], the answer for the query (L,R)=( jS + 1 , i ). For a fixed j,
all the blockAns[ j ][ i ] can be computed in O(N) time.
Now, to answer a query ( L,R ), first find the blocks jL and jR where L and R belong in (0≤ jL,jR< B). Then the answer is at least
blockAns[ jL + 1][ R], and the only pairs (x,y) not yet considered are those where L ≤ x ≤ jL +S. To consider those, one can simply try
all x in that range, and find the highest y≤R such that Ax=Ay. Finding that y can be done by using lastInBlocks[ jR−1 ][ x ] and a
series of next calls. To make that last part run in O(S) time, consider only the x such that prev[ x ] < L.
EXPLANATION:
We’ll explain the solution for subtask 1 first, because our solution for subtask 2 will build upon it. However, we will first make
the assumption that M≤N, otherwise we can simply replace the values A1,…AN with numbers from 1 to N, and should only take O(N) time
with a set. However, we don’t recommended that you actually do it; this is only to make the analysis clearer.
O(N^2) per query
First, a simple brute-force O(N^2)-time per query is very simple to implement, so getting the first subtask is not an issue at all.
I’m even providing you with a pseudocode on how to do it 
def answer_query(L, R):
for d in R-L...1 by -1
for x in L...R-d
y = x+d
if A[x] == A[y]
return d
return 0
We’re simply checking every possible answer from [0,R−L] in decreasing order. Note that the whole algorithm runs in O(Q*N^2) time, which
could get TLE if the test cases were stronger. But in case you can’t get your solution accepted, then it’s time to optimize your query time to…
O(N) per query
To obtain a faster running time, we have to use the fact that we are finding the maximum |x−y|. What this means is that for every value v,
we are only concerned with the first and last time it occurs in [L,R].
We first consider the following alternative O(N^2)-time per query solution:
def answer_query(L, R):
answer = 0
for y in L...R
for x in L...y
if A[x] == A[y]
answer = max(answer, y - x)
return answer
The idea here is that for every y, we are seeking Ax, which is the first occurrence of Ay in [L,y], because all the other occurrences will
result in a smaller y−x value. Now, to speed it up, notice that we don’t have to recompute this x every time we encounter the value Ax, because
we are already reading the values AL,…,AR in order, so we already have the information “when did Ay first appear” before we ever need it! Here’s
an implementation (in pseudocode):
def answer_query(L, R):
index = new map/dictionary
answer = 0
for y in L...R
if not index.has_key(A[y])
index[A[y]] = y
answer = max(answer, y - index[A[y]])
return answer
Now, notice that this runs in O(N) time if one uses a hash map for example!
We mention here that it’s possible to drop the use of a hash map by using the fact that the values Ay are in [1,M]. This means that we can simply
allocate an array of length M, instead of creating a hash map from scratch or clearing it. However, we must be careful when we reinitialize this array,
because it is long! There are two ways of “initializing” it:
We clear the array every time we’re done using it, but we only clear those we just encountered. This required listing all the indices we accessed.
We maintain a parallel array that contains when array was last accessed for each index. To clear the array, we simply update the current time.
We’ll show how to do the second one:
class LazyMap:
index[1..M]
found[1..M] // all initialized to zero
time = 0
def clear():
this.time++
def has_key(i):
return this.found[i] == this.time
def set(i, value): // called on the statement x[i] = value for example
this.found[i] = this.time
this.index[i] = value
def get(i): // called on the expression x[i] for example
return this.index[i]
index = new LazyMap()
def answer_query(L, R):
index.clear()
answer = 0
for y in L...R
if not index.has_key(A[y])
index[A[y]] = y
answer = max(answer, y - index[A[y]])
return answer
Using this, the algorithm still runs in O(N) time (remember that we assume M≤N), but most likely with a lower constant.
The overall algorithm runs in O(Q*N) time.
sqrt decomposition
When one encounters an array with queries in it, there are usually two ways to preprocess the array so that the queries
can be done in sublinear time:
sqrt decomposition, which splits up the array into ceiling)(N/S) blocks of size S each. S is usually taken to be floor(sqrt(N))
(hence the term “sqrt decomposition”). Usually, one can reduce the running time to O((N+Q)sqrt(N)) or O((N+Q)sqrt(NlogN)).
Sometimes, depending on the problem, it may also yield O((N+Q)N^2/3) time.build some tree structure on top of the array.
This usually yields an O(N+QlogN)O(N+QlogN) or O((N+Q)logN)O((N+Q)logN) time algorithm.There are other less common ways, such as
lazy updates or combinations of the above, but first we’ll try out whether the above work.
Suppose we have selected the parameter S, and we have split the array into B=celing(N/S) blocks of size S, except possibly the
last block which may contain fewer than S elements. Suppose we want to answer a particular query (L,R). Note that L and R will
belong to some block. For simplicity, we assume that they belong to different blocks, because if they are on the same block, then R−L≤S,
so we can use the O(S) time query above.
Thus, the general picture will be:
|…|…|…|…|…|…|…|
^ ^ ^ ^
L E_L E_R R
We have marked two additional points, EL and ER, which are the boundaries of the blocks completely inside [L,R]. Now, it would be nice
if we have already precomputed the answer for the query pair (EL,ER), because then we will only have to deal with at most 2(S−1) remaining
values: [L,EL) and [ER,R]. We can indeed precompute the answers at the boundaries, but we can do even better: we can precompute the
answers for all pairs (E,R), where EE is a boundary point and RR is any point in the array! There are only O(BN) pairs, and we can compute
the answers in O(BN) time also:
class LazyMap:
…
S = floor(sqrt(N))
B = ceil(N/S)
index = new LazyMap()
blockAns[1..B][1..N]
def precompute():
answer = 0
for b in 1...B
index.clear()
E = b*S-S+1 // left endpoint of the b'th block
answer = 0
for R in E...N
if not index.hasKey(A[R])
index[A[R]] = R
answer = max(answer, R - index[A[R]])
blockAns[b][R] = answer
(if you read the “quick explanation”, note that there is a slight difference here: we’re indexing the blocks from 1 to B instead of 0 to B−1)
This means that, in the query, the only remaining values we haven’t considered yet are those in [L,EL). To consider those, we have to know,
for each x in [L,EL), the last occurrence of Ax in [L,R]. To do so, we will need the following information:
next[i], the smallest j>i such that Ai=Aj
prev[i], the largest j<i such that Ai=Aj
lastInBlocks[j][i], the largest k within the first j blocks such that Ak=Ai
Checking whether an Ax has been encountered before can also be done using the index approach, or alternatively as prev[x]≥L:
def answer_query(L, R):
b_L = ( ( L + S - 1 ) / S )
b_R = R / S
if b_L >= b_R
// old query here
else
E_L = b_L*S
answer = blockAns[b_L+1][R]
for x in L...E_L
if prev[x] < L # i.e. x hasn't been encountered before
y = lastInBlocks[floor(R/S)][x]
while next[y] < = R
y =next[y]
answer = max(answer, y - x)
return answer
One can now see that the query time is now O(S) Note that bL≤bR means that L and R are within O(S) elements away, so we can do the old
query instead.
Let’s now see how to precompute next, prev and lastInBlocks. First, next[i] and prev[i] can easily be computed in O(N) time with the following code:
…
next[1…N]
prev[1…N]
last[1…M] // initialized to 0
…
def precompute():
…
for i in 1...N
next[i] = N+1
prev[i] = 0
for i in 1...N
j = last[A[i]]
if j != 0
next[j] = i
prev[i] = j
last[A[i]] = i
The last array stores the last index encountered for every value, and is updated as we traverse the array.
And then lastInBlocks can be compute in O(BN) time:
…
lastInBlocks[1…B][1…N] // initialized to 0
…
def precompute():
for b in 1...B
L = b*S-S+1
R = min(b*S,N)
for y in L...R
if next[y]>R
x = y
while x>0
lastInBlocks[b][x] = y
x = prev[x]
for x in 1...N
for b in 2...B
if lastInBlocks[b][x] == 0
lastInBlocks[b][x] = lastInBlocks[b-1][x]
The first loop finds the last value encountered at each block (with the check next[y] > R), and proceeds
setting the lastInBlocks of all the indices until that position with equal value, using the prev pointer.
The second loop fills out the remaining entries, because some values do not have representatives in some blocks.