PROBLEM LINK:
Author: Tuan Anh Tran Dang
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Segment Tree
PROBLEM:
Maintain 2 arrays, A[1…N], B[1…N], supporting 3 types of operations:
- A[i] = min{A[i], (i - l) * a + b}
- B[i] += (i - l) * a + b
- print A[i] + B[i]
There are Q operations in total.
EXPLANATION:
Because the only output is A[i] + B[i], and there are no “crossing” operations, we can treat A[] and B[] separately.
For B[] side, it is much easier. First, we can re-write the formula to
B[i] += i * a + l * a + b
, which is also equivalent to
B[i] += i * a' + b'
And, it is worth noting that,
(i * a + b) + (i * c + d) = i * (a + c) + (b + d)
Therefore, we can maintain a segment tree whose node records the interval adds. That is, for each node, which represents interval [l…r], we record the sum of a and b, which are added to the whole interval. And when querying B[i], we can sum up all sum of node on the path from root [1, N] to the leaf [i, i].
All operations related to B[] can be done in O(logN) time.
For A[] side, the idea a little tricky, but I think it is also easy to follow. For each node, which represents interval [l…r], we record a pair of a and b, which means for all i (l <= i <= r), A[i] should be smaller than i * a + b. When a new pair a’, b’ comes, because the two curves are linear, there should be at most one intersection. This is a very important and beautiful fact – it implies that, there are 2 cases:
- a’, b’ are totally better or totally worse than a, b. That is, for all i (l <= i <= r), a * i + b <= a’ * i + b’, or for all i (l <= i <= r), a * i + b >= a’ * i + b’.
- In at least one of [l, m] and [m + 1, r], the situation will fall in the Case 1.
Therefore, we can recursively update the children, if we are in the Case 2. For the query, we can get the minimum of the nodes on the path from root [1, N] to the leaf [i, i]. And the time complexity is O(logN) too.
Due to the large scale of N, we can not build the whole segment tree. But we can create the nodes, which are related to the queries. With this idea in mind, we can implement a solution using only O(QlogN) memory. Because, for each operation, only O(logN) nodes are related.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.