Clash Wildcard - Tyrion and Triplet (CLWI21E) - EDITORIAL

Practice

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

Solution

5 Likes

@mufa_ddal
I tried to do it with simple segment tree without using the Lazy propagation.
But it showing TLE .Can u plz tell me where did I messed up…

My Code : Solution: 42147787 | CodeChef

I don’t know your approach, understanding the code is very difficult

@mufa_ddal
My approach was basically that, we are adding a squared series from L to R.
If we need to know value to be added to a position in the range L to R equals to
(pos-L+1)^2 , on expanding, pos^2 + (L-1)^2 - 2^(L-1)(pos). so I thought we can maintain
summation of (L-1)^2 and (L-1) for ranges …And later we can get the contribution of any range by some calculations…So I really don’t have any idea , why is it giving TLE.

Oh so you are storing L for all indices in range [L, R] for all the queries 2
In worst case, say Q/2 queries have one intersecting index i, and later there are Q/2 queries of type 1 querying at this index all the time, so the complexity for query 1 would be around O(Q) because you calculate updation at i_{th} index for all update queries Q/2 . So time in worst case is turning out to be O(Q^2) which definitely is TLE.

1 Like

@mufa_ddal
I am doing everything using a segment tree. So aren’t all the operations of O(LogN) complexity!!

U can have a look at my this submission…
A bit easier to understand I guess

I can’t understand others codes. I can only help with logic. Try rechecking the code if you are confident about your solution. Maybe some termination condition in recursions.

1 Like

@mufa_ddal
Ok thanks …

Excellent problem and a much needed editorial! Thanks!

1 Like

I saw your solution
Your update time is not logn it is (logn)^2
Because you are calling power function that takes log(10^9) in it for each depth basically worse than (logn)^2
Find a constant value before and later convert that power function to a constant one

Thank you!

Thank you so much man :sweat_smile: …
It passes with ease now…