Problem Description
This is a more difficult version of "minimum". In this problem, instead of just finding the minimum of an entire array, the array can now change! Between the updates of the array, there will be requests for the minimum value of the current array.
In fact, your program will have to implement the following functions:
- void loadArray(int N, int A[]);, which is called at the start of the program that tells you the initial array A of length N.
- void update(int P, int V);, which updates the number at position P to value V.
- int findMin();, which returns the minimum value within the current array.
To aid you, you have been provided with a special array with extraordinary capabilities, in particular the functions:
- void ArrayInsert(int N), which adds an element to the array.
- void ArrayRemove(int N), which removes one element with the value N from the array.
- int ArraySize(), which returns the number of elements in the array.
- int SmallestElement(), which returns the smallest number in the array.
Input
Refer to the "minimum" input description.
Output
Refer to the "minimum" output description.
Limits
Subtask 1 (35%): 1 <= N <= 1 000
Subtask 2 (65%): 1 <= N <= 1 000 000
update() and findMin() will at most be called N times.