5647: CF EDU - Segment Tree P1 - Step 1 - C. Number of Minimums on a Segment
[Creator : ]
Description
Now change the code of the segment tree so that, in addition to the minimum on a segment, it also counts the number of elements equal to the minimum.
Input
The first line contains two integers $n,\ m (1≤n,\ m≤100,000)$, the size of the array and the number of operations.
The next line contains $n$ numbers $a_i$, the initial state of the array $(0≤a_i≤10^9)$.
The following lines contain the description of the operations. The description of each operation is as follows:
The next line contains $n$ numbers $a_i$, the initial state of the array $(0≤a_i≤10^9)$.
The following lines contain the desc
- ${1\ i\ v}$: set the element with index $i$ to $v$ $(0≤i<n,\ 0≤v≤10^9)$.
- ${2\ l\ r}$: calculate the minimum and number of elements equal to minimum of elements with indices from $l$ to $r-1$ $(0≤l<r≤n)$.
Output
For each operation of the second type print two integers: the minimum on a segment, and the number of elements equal to minimum.
Sample 1 Input
5 5
3 4 3 5 2
2 0 3
1 1 2
2 0 3
1 0 2
2 0 5
Sample 1 Output
3 2
2 1
2 3