## 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";↵
```↵
↵
↵
↵
### 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**.↵
↵
---↵
↵
↵
---↵
https://codeforces.me/contest/2175/problem/B↵
↵
### Idea: Reconstruct the Array Using Prefix XOR↵
↵
Sometimes we **don’t know the array `a` directly**, but we **know how its prefix XOR array should look**.↵
In that case, the trick is:↵
↵
1. **Construct a valid prefix XOR array `p`**↵
2. **Recover the original array `a` from it**↵
↵
---↵
↵
### Key Observation↵
↵
If↵
[↵
p[i] = a[1] \oplus a[2] \oplus \dots \oplus a[i]↵
]↵
↵
then:↵
[↵
a[i] = p[i] \oplus p[i-1]↵
]↵
↵
So once `p` is known, `a` is uniquely determined.↵
↵
---↵
↵
### Constructing the Prefix Array `p`↵
↵
We build an array `p` that represents **how the prefix XOR of `a` should look**:↵
↵
* `p[0] = 0`↵
* For all indices:↵
↵
* `p[i] = i`↵
* Except at position `r`, where `p[r] = l - 1`↵
↵
```cpp↵
int n, l, r;↵
cin >> n >> l >> r;↵
↵
vector<int> p(n + 1);↵
p[0] = 0;↵
↵
for (int i = 1; i <= n; i++) {↵
if (i == r)↵
p[i] = l - 1;↵
else↵
p[i] = i;↵
}↵
```↵
↵
---↵
↵
### Recovering Array `a`↵
↵
Using the XOR relation:↵
↵
```cpp↵
vector<int> a(n + 1);↵
↵
for (int i = 1; i <= n; i++) {↵
a[i] = p[i] ^ p[i - 1];↵
cout << a[i] << " ";↵
}↵
```↵
↵
---↵
↵
### Why This Works↵
↵
* XOR is **reversible**.↵
* Knowing consecutive prefix values is enough to reconstruct the original array.↵
* This technique is very common in problems involving **prefix XOR constraints**.↵
↵
---↵
↵
↵
`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";↵
```↵
↵
↵
↵
### 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**.↵
↵
---↵
↵
↵
---↵
https://codeforces.me/contest/2175/problem/B↵
↵
### Idea: Reconstruct the Array Using Prefix XOR↵
↵
Sometimes we **don’t know the array `a` directly**, but we **know how its prefix XOR array should look**.↵
In that case, the trick is:↵
↵
1. **Construct a valid prefix XOR array `p`**↵
2. **Recover the original array `a` from it**↵
↵
---↵
↵
### Key Observation↵
↵
If↵
[↵
p[i] = a[1] \oplus a[2] \oplus \dots \oplus a[i]↵
]↵
↵
then:↵
[↵
a[i] = p[i] \oplus p[i-1]↵
]↵
↵
So once `p` is known, `a` is uniquely determined.↵
↵
---↵
↵
### Constructing the Prefix Array `p`↵
↵
We build an array `p` that represents **how the prefix XOR of `a` should look**:↵
↵
* `p[0] = 0`↵
* For all indices:↵
↵
* `p[i] = i`↵
* Except at position `r`, where `p[r] = l - 1`↵
↵
```cpp↵
int n, l, r;↵
cin >> n >> l >> r;↵
↵
vector<int> p(n + 1);↵
p[0] = 0;↵
↵
for (int i = 1; i <= n; i++) {↵
if (i == r)↵
p[i] = l - 1;↵
else↵
p[i] = i;↵
}↵
```↵
↵
---↵
↵
### Recovering Array `a`↵
↵
Using the XOR relation:↵
↵
```cpp↵
vector<int> a(n + 1);↵
↵
for (int i = 1; i <= n; i++) {↵
a[i] = p[i] ^ p[i - 1];↵
cout << a[i] << " ";↵
}↵
```↵
↵
---↵
↵
### Why This Works↵
↵
* XOR is **reversible**.↵
* Knowing consecutive prefix values is enough to reconstruct the original array.↵
* This technique is very common in problems involving **prefix XOR constraints**.↵
↵
---↵
↵
