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