Task NORMA Author: Ivan Katanić
The goal of this task is, for each two integers A and B (1 <= A <= B <= N),
calculate the price of the subsequence [A,B] of input array X and to sum up
the given values. Let us imagine that we are moving the right bound B from
left to right and maintaining the array of solutions for current B, so that at
position A of that array, call it array T, there is the price of subsequence [A,B].
A high-level algorithm would look like this:
initialize array T to 0
solution = 0
for B from 1 to N
subsequences are expanded from [A,B1]
to [A,B] by adding
X[B]
therefore refresh values in array T at positions 1 to B
add to the solution T[1] + T[2] + … + T[B]
Let’s imagine that every member T[A] of array T internally contains values m,
M and L, minimal number of sequence [A,B], maximal number of sequence
[A,B] and length of subsequence [A,B], respectively.
We need to have an efficient update of values (prices) in array T. Since the
value of a member is the product of its internal values, let us observe how
these are changing when incrementing B by 1 (moving to the right). Values L
of each member with index smaller than or equal to B are incremented by 1.
Let Pm be the position of the rightmost member of array X that is to the left of
B such that it holds X[Pm] < X[B]. Value m of all members of array T at
position from the interval [1,Pm] will be left unchanged while the value m of all
members of array T on positions from the interval [Pm+1,B] will become
exactly X[B].
Similarly, PM be the position of the rightmost member of array X that is to the
left of B such that it holds X[PM] > X[B]. Value M of all members of array T at
position from the interval [1,PM] will be left unchanged while the value M of all
members of array T on positions from the interval [PM+1,B] will become
exactly X[B].
Therefore, it is necessary to implement a data structure that will allow the
following operations:
increment_L(lo, hi, d_L) - increment value L by d_L to all members of the
array at position from the interval [lo,hi].
set_m(lo, hi, new_m) - set value m to new_m to all member of the array at
position from the from the interval [lo,hi].
set_M(lo, hi, new_M) - set value M to new_M to all member of the array at
position from the from the interval [lo,hi].
sum_mML(lo, hi) - return the sum of products of values m, M and L of all the
members of the array at position from the interval [lo, hi].
It turns out that the required operations can be efficiently achieved using a
tournament tree. For this purpose, every node of the tree must contain the
following values:
len - length of the interval of members of the array that the node is covering,
for example, for leaves it holds len=1
sm - sum of values m of all members from the interval
sM - sum of values M of all members from the interval
sL - sum of values L of all members from the interval
smM - sum of values m*M of all members from the interval
smL - sum of values m*L of all members from the interval
sML - sum of values M*L of all members from the interval
smML - sum of values m*M*L of all members from the interval
How would incrementing values L to all members from the interval belonging
to the node of the tree look like?
It is necessary to suitably change the value of each node in the following way:
sL = sL + d_L * len
smL = smL + sm * d_L
sML = sML + sM * d_L
smML = smML + smM * d_L.
Let’s observe how setting values m to all members from the interval belonging
to the node of the tree looks like:
sm = new_m * len
smM = new_m * sM
smL = new_m * sL
smML = new_m * sML.
And, finally, setting values M to all members from the interval belonging to the
node of the tree:
sM = new_M * len
smM = new_M * sm
smL = new_M * sL
smML = new_M * smL.
Because of the fact that all values in the nodes are sums, merging two nodes
of a child for the purpose of calculating values of the parent node is simply the
summation of the corresponding values from both nodes.
The nature of mentioned operations on the structure is such that it is
necessary to use tournament tree with propagation. The details of this
expansion are general and left out from this description, but can be looked up
in the attached code.
We are still left with efficiently finding the rightmost smaller or larger number
than the current X[B]. This can be simply implemented using a stack. Here we
will describe finding the rightmost smaller value that is to the left of X[B], and
finding the rightmost larger value is done in a similar manner.