Range Variation Query#695
The sequence a_n is defined by the following formula:
It is necessary to repeatedly handle requests of two types:
Find the difference between the maximum and minimum values among the elements a_i, a_{i+1}, \ldots, a_j;
Assign the element a_i a new value .
The first line contains one natural number (k \le 10^5) — the number of requests.
Each of the following lines describes one request with two integers x_i and y_i:
If x_i > 0, it is necessary to find the difference between the maximum and minimum values in the segment a_{x_i} \ldots a_{y_i} (1 \le x_i \le y_i \le 10^5).
If x_i < 0, it is necessary to assign the element a_{-x_i} (-10^5 \le x_i \le -1) the value y_i (|y_i| \le 10^5).
For each request of the first type, output on a separate line the difference between the maximum and minimum values on the specified segment.
Example 1