2005. The Largest in a Range and How Often It Appears
An array of n integers is given, numbered from 1. Then q operations arrive:
set i v replace position i with v
max l r print two integers: the largest value in positions l to r, and how
many positions in that range hold it
3 1 4 1 5
max 1 5 -> 5 1
set 2 5 the array becomes 3 5 4 1 5
max 1 5 -> 5 2
max 2 2 -> 5 1
## What most people try first
Run the segment tree of problem 2004 for the maximum, then make a second pass
over the range to count how many equal it. The maximum is O(log n) and the
count is O(r - l + 1), so the pair costs as much as scanning, and the tree has
bought nothing.
The fix is not a second structure. It is to notice that the COUNT can be carried in the same node as the maximum, if the merge is defined to carry it.
## A node that holds a pair
Let each node hold (best, howMany) for its range, and merge two children:
merge(x, y):
if x.best > y.best: return x
if y.best > x.best: return y
return (x.best, x.howMany + y.howMany)
A leaf is (value, 1).
## Why this is still a valid segment tree
A segment tree needs only that the merge be ASSOCIATIVE, so that splitting a range into nodes in any way gives the same result.
This one is. Take any three nodes. If one strict maximum is largest, both groupings return it with its own count. If several tie for largest, both groupings return that value with the sum of exactly the tied counts, because addition is associative and the non-maximal counts are discarded in both orders. So the tree may split the range however it likes.
That is the general lesson: to answer a harder question, widen what a node stores until the merge closes over it. The structure does not change at all.
## The boundary that breaks a careless implementation
The two equal branches. Writing the merge with >= in the first test returns
x whenever the values tie, silently dropping y.howMany, so every tie reports
a count of 1. That version is right about the maximum in every case and wrong
about the count in exactly the cases the problem is about.
The identity element needs the same care: it must be (something smaller than
any value, 0). A count of 1 in the identity adds a phantom occurrence.
Values reach -10^9, so the identity's value must be below that; the test of
three negatives exists to catch an identity of 0.
## Cost
O(log n) per operation, the same as 2004, because the node is larger but the
number of nodes visited is unchanged. About 3.6 * 10^6 node visits at the
limits.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `-10^9 ≤ each value ≤ 10^9` - `1 ≤ i ≤ n` and `-10^9 ≤ v ≤ 10^9` - `1 ≤ l ≤ r ≤ n`
Input
The first line contains two integers n and q.
The second line contains n integers, the starting values.
Each of the next q lines is either set i v or max l r.
Output
For every max operation print one line holding two integers separated by a single space: the largest value in the range, then how many positions in that range hold it. A set prints nothing.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.