Author: Mufaddal
DIFFICULTY:
MEDIUM to HARD.
PREREQUISITES:
Maths, Lazy Propogation
Problem:
You are given an array A of N positive integers and Q queries.
Each query is either of type 1 or type 2 :
1 L R : For each query of this type, find sum of all possible combinations of A[i] \times A[j] \times A[k] such that i is in range [1, L], j is in the range [L+1, R], and k is in the range [R+1, N]. Print the answer modulo 10^9 + 7
2 L R : For a query of this type, you have to perform following operation:
A[L] := A[L] + 1^2,
A[L+1] := A[L+1] + 2^2,
\dots
A[L+k] := A[L+k] + (k+1)^2,
\dots
A[R] := A[R] + (R-L+1)^2
Explanation:
For the explanation of both the queries, I’ll be talking about array being split in 3 segments namely - left [1, L], middle [L+1, R] and right [R+1, N].
Query 1 :
A little observation is enough to understand that the answer to this query is basically the product of sum of elements in left segment with that in middle and right segment.
So ans to this query is \sum_{i=1}^{L} A_i \times \sum_{j = L+1}^{R} A_j \times \sum_{k = R+1}^{N} A_k.
We create the prefix sum array, so now we have pref_i = \sum_{j=1}^{i} A_j which can be created in O(N).
Query 2
This type of Query can be performed in O(N - L) (remember we have to update the pref array and not the original one) but given the constraints, we would get TLE.
Left Segment
When performing this query, it can be seen that the prefix sum array values in range [1, L) are not getting affected.
Middle Segment
Values in prefix sum array are updated as follows in the range [L, R]:
pref_i = pref_i + \sum_{j=L}^{i} (j - L + 1)^2
which can be re-written as
pref_i = pref_i +\frac {y_i}{6}
y_i=x (x+1) (2(x+1) +1) , where x = i - L + 1
y_i can be re-written as:
y_i = ai^3 + bi^2 + ci+d \dots (1)
where
a = 2
b = -6L + 9
c = 6L^2 - 18L + 13
d = -2L^3 + 9L^2 -13L + 6
Note that these values are going to be different for different queries
Right Segment
We have to add a constant value x to prefix sum array in range [R+1, N]
x = \sum_{j=L}^{R} (j - L + 1)^2
or
x = \frac{y \times (y+1) \times (2(y+1) +1)}{6} , where y = R - L + 1
So when we have query of type 2,
-
we do not make any changes to left segment,
-
we add a constant value to the right segment. This can be done easily using Lazy propagation or Fenwick Tree.
Say we have some queries of type 2
[l1, r1], [l2, r2], [l3, r3]
let some indices lie in the intersecting interval [l, r] of these three intervals
then y_i = \sum_{j=1}^{3}{a_ji^3 + b_ji^2 + c_ji + d_j}, \forall{i} \subset [l, r]
We can see that the coefficients for different queries add up for each i.
so we can write y_i in general as:
y_i = i^3{\sum_{j \subset Z_i}{a_j}} + i^2{\sum_{j \subset Z_i}{b_j}} +i{\sum_{j \subset Z_i}{c_j}} + i^3{\sum_{j \subset Z_i}{d_j}}
Z_i is a set of indices of queries of type 2 such that i \subset [l_k, r_k] for each query k that has already been worked upon.
let’s store the summation of a_k, b_k, c_k, d_k for all indices separately.
So now when we have a query [l, r] of type 2, we calculate a, b, c, d for that query and add a, b, c, d to the corresponding values sum_a, sum_b, sum_c, sum_d for all indices in range [l, r]. This can be done using lazy propogation.
Query of type 1 and 2 can now be performed in O(log(n)).
…