PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Danny Boy
Tester: Harris Leung
Editorialist: Pratiyush Mishra, Jakub Safin
DIFFICULTY:
Easy-medium
PREREQUISITES:
Segment trees
PROBLEM:
You should perform queries on a sequence A. In each query, you either change an element A_i or need to find the smallest K such that |A_L-K|, |A_{L+1}-K|, \ldots, |A_R-K| is sorted in non-decreasing order (or determine that no such K exists).
EXPLANATION:
Let’s reformulate a condition |A_i-K| \le |A_{i+1}-K|. There are three distinct cases:
- A_i = A_{i+1}: the condition is always true
- A_i \lt A_{i+1}: we need K \le (A_{i+1}+A_i)/2
- A_i \gt A_{i+1}: we need K \ge (A_{i+1}+A_i)/2
It’s easy to see because the condition says simply “K cannot be closer to A_{i+1} than A_i”.
In addition, we’re looking for K \ge 0 and clearly won’t ever need K \gt M = 10^9 (M is the upper bound on elements of A). That means we can create and keep updating a new sequence of ranges [l_1, r_1], \ldots, [l_{N-1},r_{N-1}], where:
- if A_i = A_{i+1}, then l_i = 1 and r_i = M
- if A_i \lt A_{i+1}, then l_i = 1 and r_i = (A_{i+1}+A_i)/2
- if A_i \gt A_{i+1}, then l_i = (A_{i+1}+A_i)/2 and r_i = M
For each query of type 1, at most two of these values need to be updated. These ranges determine allowed values of K, so in a query of type 2, we just need to find x = \max(l_L, \ldots, l_{R-1}) and y = \min(r_L, \ldots, r_{R-1}). Then:
- if x \gt y, there is no possible K
- if x \le y, any K in the range [x,y] satisfies the condition; we’re looking for the minimum, which is K = x
Finding the minima and maxima of ranges, along with updating single elements, is done efficiently by several well-known data structures like segment tree.
TIME COMPLEXITY:
We use two segment trees, perform O(1) operations in each tree for each query, so the time complexity is O((N+Q) \log N).
