↵
Since `std::map` is sorted by keys, not values, you can use `std::max_element` to find the pair with the largest value:↵
↵
```cpp↵
auto it = max_element(↵
m.begin(), m.end(),↵
[](const auto &a, const auto &b) {↵
return a.second < b.second;↵
}↵
);↵
↵
cout << "Max value: " << it->second << " (Key: " << it->first << ")" << endl;↵
```↵
↵
**Explanation:**↵
↵
* `std::max_element` iterates through all pairs.↵
* The lambda compares elements based on their `second` value.↵
* The iterator `it` points to the pair with the maximum value.↵
↵
---↵
↵
### Bonus↵
↵
If you want the maximum key instead, you can write:↵
↵
```cpp↵
auto last = m.rbegin();↵
cout << last->first << " " << last->second;↵
```↵
↵
---↵
↵
Tip: Counting Distinct Elements in All Prefixes↵
↵
When a problem asks you to count distinct numbers before (or up to) each index, think in terms of prefix processing + frequency tracking.↵
↵
Idea:↵
Stand at each index i and maintain a frequency array (or map).↵
↵
If the current element appears for the first time, then the number of distinct elements increases by one.↵
↵
Store this count as the number of distinct elements in the prefix ending at i.↵
↵
Implementation Sketch:
## Find the Maximum Value in a `std::map`↵
↵
`std::map` is ordered by **keys**, not by **values**.↵
To find the element with the **maximum value**, use `std::max_element`.↵
↵
### Code↵
↵
```cpp↵
auto it = max_element(↵
m.begin(), m.end(),↵
[](const auto &a, const auto &b) {↵
return a.second < b.second;↵
}↵
);↵
↵
cout << "Max value: " << it->second↵
<< " (Key: " << it->first << ")\n";↵
```↵
↵
### Explanation↵
↵
* `std::max_element` scans all key–value pairs.↵
* The lambda compares pairs using their `second` (value).↵
* The returned iterator points to the pair with the **largest value**.↵
↵
### Bonus: Maximum Key↵
↵
Since `std::map` is sorted by key:↵
↵
```cpp↵
auto last = m.rbegin();↵
cout << last->first << " " << last->second;↵
```↵
↵
---↵
↵
## Tip: Counting Distinct Elements in All Prefixes↵
↵
When a problem asks for the number of **distinct elements before or up to each index**, use **prefix traversal + frequency tracking**.↵
↵
### Idea↵
↵
* Traverse the array from left to right.↵
* Maintain a frequency map (or array).↵
* When an element appears **for the first time**, increase the distinct count.↵
* Store this count for each prefix.↵
↵
### Implementation↵
↵
```cpp↵
map<int, int> freq;↵
vector<int> distinct(n);↵
int cnt = 0;↵
↵
for (int i = 0; i < n; i++) {↵
cnt++; // new distinct element↵
}↵
```↵
↵
↵
```cpp↵
long long ans = 0;↵
for (int i = 0; i < n; i++) {↵
ans += distinct[i];↵
}↵
```↵
↵
### Why
↵
Each element contributes to the distinct count
↵
↵
↵
---↵
↵
If you want:↵
↵
* an **even shorter CF-style tip**,↵
* or both tips merged into a **“Useful STL & Prefix Tricks”** post↵
just tell me ↵
