---↵
https://codeforces.me/contest/2175/problem/A↵
↵
## 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**.↵
↵
---↵
Custom Comparator for Pairs: Sort by Sum↵
Tip: Sort pairs in descending order based on sum of elements.↵
Implementation:↵
cpp sort(vec.begin(), vec.end(), [](const pair<int,int> &a, const pair<int,int> &b) {↵
return (a.first + a.second) > (b.first + b.second);↵
});↵
↵
---↵
↵
Check Parity: Same or Different Even/Odd↵
Check if two numbers have different parity:↵
cppif ((a ^ b) & 1) {↵
// a and b have different parity (one even, one odd)↵
}↵
↵
---↵
https://codeforces.me/contest/2175/problem/A↵
↵
## 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**.↵
↵
---↵
Custom Comparator for Pairs: Sort by Sum↵
Tip: Sort pairs in descending order based on sum of elements.↵
Implementation:↵
cpp sort(vec.begin(), vec.end(), [](const pair<int,int> &a, const pair<int,int> &b) {↵
return (a.first + a.second) > (b.first + b.second);↵
});↵
↵
---↵
↵
Check Parity: Same or Different Even/Odd↵
Check if two numbers have different parity:↵
cppif ((a ^ b) & 1) {↵
// a and b have different parity (one even, one odd)↵
}↵
↵
---↵
