PROBLEM LINK:
Author: Sergey Kulik
Testers: Vasya Antoniuk and Kevin Atienza
Translators: Vasya Antoniuk (Russian), Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Medium
PREREQUISITES:
Cross product, persistent segment trees
PROBLEM:
You are given two arrays A and B, each consisting of N integers.
You are also given M queries of the form L_j R_j C_j D_j. For each of these queries, we ask you to calculate the value of the sum of \max(0, A_i C_j - B_i D_j) over i from L_j to R_j.
This is an online problem, so you won’t get the next query unless you answer the current one.
QUICK EXPLANATION:
Construct N 2D vectors: \vec{v_i} = \langle A_i, B_i \rangle for every 1 \le i \le N. Note that all vectors point in the first quadrant.
For the purposes of this solution, the cross product of two vectors \langle x_i, y_i \rangle and \langle x_j, y_j \rangle is x_iy_j - x_jy_i.
A vector \vec{w} is counterclockwise of \vec{v} if \vec{w} \times \vec{v} is positive. Two vectors point at the same direction if their cross product is 0. With this in mind, collect all distinct nonzero directions of all $v_i$s, sort them all counterclockwise, and form a persistent segment tree on top of them that can support range sums of vectors. Let T_i be the tree where \vec{v_1}, \vec{v_2}, \ldots, \vec{v_i} have been inserted already. Each T_i can be obtained from T_{i-1} by inserting \vec{v_i} to it persistently. But if \vec{v_i} = \langle 0,0 \rangle, simply don’t insert \vec{v_i} at all.
A query on a tree T_i consists of a vector \vec{v}, and the result is the sum of all vectors in T_i that are clockwise to \vec{v}. We denote this by T_i(\vec{v}).
To answer a query, let \vec{v} = \langle D_j, C_j \rangle. Also, let \vec{w} = T_{R_j}(\vec{v}) - T_{L_j-1}(\vec{v}). Then the answer is \vec{w}\times \vec{v}.
EXPLANATION:
Let’s first answer the offline version of the problem, which should be easier. Also, let’s denote by F(L,R,C,D) the answer for the query with values (L,R,C,D), that is, the sum of \max(0, A_i C - B_i D) over i from L to R. Thus, the answer for the j th query is F(L_j,R_j,C_j,D_j).
Note that if were to add, say, A_i C_j - B_i D_j instead of \max(0, A_i C_j - B_i D_j), then this would be easier, because we can simply perform a range sum in the arrays in A and B in the range [L_j,R_j] and multiply then by C_j and D_j. Range sums can be handled by first precomputing prefix sums and then, for each range sum query, finding two corresponding prefix sums and subtracting them.
However, the problem is that we only need to add the A_i C_j - B_i D_j terms that are positive. When is this term positive? Notice that this term is positive if and only if \frac{B_i}{A_i} < \frac{C_j}{D_j}. This means that, if we consider each pair of values \langle A_i, B_i \rangle as a vector, then we only need to consider those vectors whose slope are at most \frac{C_j}{D_j}!
Performing the comparison \frac{B_i}{A_i} < \frac{C_j}{D_j} has a few caveats though. First, this doesn’t work if A_i or D_j is zero. So instead of doing that, you should compare A_i C_j < B_i D_j instead when comparing angles, which doesn’t need division. Next, it may happen that A_i = B_i = 0 or C_j = D_j = 0, but in these cases, the contribution towards the sum is 0, so we may safely ignore them.
This suggests to us that we should arrange the vectors \langle A_i, B_i \rangle according to angle instead. Unfortunately, this doesn’t work too, because for each query we only need co consider vectors with indices i \in [L_j, R_j], and once we order them in another way, the indices will all get messed up!
To solve the offline problem, we need a few more insights. The first is that we can decompose the query F(L,R,C,D) into two prefix queries using the following formula:
This follows from the fact that for any x < y \le z, F(x,z,C,D) = F(x,y-1,C,D) + F(y,z,C,D), because [x,z] = [x,y-1] \cup [y,z]. Thus, we just need to compute 2Q prefix sum queries, i.e., queries of the form F(1,i,C,D).
Next, we can process these prefix sum queries by inserting the vectors one by one, in increasing order of i. By doing this, we ensure that, after the i th insertion, the structure contains all vectors with indices [1,i], and so we can answer all prefix sum queries of the form F(1,i,C,D)!
The following pseudocode illustrates this more clearly:
for i=1..N:
(insert <A_i,B_i> into the structure)
for all queries of the form F[1,i,C,D]:
<A,B> = (sum of all vectors in the structure with slope at most C/D)
(set A*C - B*D as the result of the query F[1,i,C,D])
The structure in this code is some structure that can handle insertion of vectors and allows for summing vectors whose slope is at most a given slope. If the structure orders the vectors according to handle, then that query becomes a prefix sum query, because all vectors with at most a given slope will surely be the first few vectors with the smallest slopes!
Finally, we need a structure that can these operations efficiently. But for this, a simple segment tree will do, but this time the segment tree contains vectors, and the comparison is angle comparison: \langle x_1, y_1 \rangle < \langle x_2, y_2 \rangle if and only if x_1y_2 - x_2y_1 > 0.
Thus, we have an algorithm that runs in O((N + M) \log N) time for the offline problem!
Unfortunately, we use this for the online version of the problem, because we don’t know all the queries beforehand. Luckily, we can modify this algorithm to solve the online version, by using persistent segment trees.
Persistent segment trees are segment trees that gives access to all their previous versions. To achieve this, when inserting a new vector \vec{v}, instead of updating the nodes in the path corresponding to \vec{v}, we copy all nodes along that path. If you don’t throw out the pointer to the old root, this allows us to keep access to the old tree!
More formally, let T_i be the persistent segment tree where the first i vectors have been inserted. Then to answer the query F(L,R,C,D), we simply compute F(1,R,C,D) - F(1,L-1,C,D), and to compute F(1,i,C,D), we simply query the tree T_i! The $T_i$s themselves can be computed beforehand with the following algorithm:
T[0] = (empty tree)
for i=1..N:
T[i] = T[i-1].insert(<A_i,B_i>)
Here, tree.insert doesn’t modify the original tree.
This algorithm still runs in O((N + M) \log N) time!
Finally, here a couple of gotchas for this algorithm.
- Your code may happen to be slow when there are zero vectors. Note that, with zero vectors, x_1y_2 - x_2y_1 is always zero, so depending on your implementation, this may cause each insertion / query to traverse the whole tree! To handle this, simply ignore zero vectors, since their contribution to the overall sum is zero anyway.
- If there are multiple vectors having the same angle, then your code might get TLE / WA because you might traverse a large part of the tree. To handle this, consider all vectors pointing to the same direction to only occupy one slot in the segment tree. Note that two vectors have the same angle if x_1y_2 - x_2y_1 = 0.
Time Complexity:
O((N + M) \log N)