↵
`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";↵
```↵
↵
↵
* `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++) {↵
if (++freq[x[i]] == 1)↵
cnt++; // new distinct element↵
distinct[i] = cnt; // distinct elements in prefix [0..i]↵
}↵
```↵
↵
### Sum of Distinct Counts Over All Prefixes↵
↵
```cpp↵
long long ans = 0;↵
for (int i = 0; i < n; i++) {↵
ans += distinct[i];↵
}↵
```↵
↵
### Why This Works↵
↵
Each element contributes to the distinct count **exactly once**, at its **first occurrence**.↵
↵
---↵
↵
↵
* an **even shorter CF-style tip**,↵
* or both tips merged into a **“Useful STL & Prefix Tricks”** post↵
just tell me ↵
