--- 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

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

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

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:

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: cppsort(vec.begin(), vec.end(), [](const pair<int,int> &a, const pair<int,int> &b) { return (a.first + a.second) > (b.first + b.second); });