Tips and Tricks

By Nourhan_Abo-Heba

Problem A: Counting Distinct Elements in Prefixes

Idea: Track distinct elements up to each index using frequency map.

Implementation: ```cpp map<int, int> freq; vector distinct(n); int cnt = 0;

for (int i = 0; i < n; i++) { if (++freq[x[i]] == 1) cnt++; distinct[i] = cnt; } ```

Sum over all prefixes: cpp long long ans = 0; for (int i = 0; i < n; i++) ans += distinct[i];

Problem B: Reconstruct Array from Prefix XOR

Key: If p[i] = a[1] ⊕ a[2] ⊕ ... ⊕ a[i], then a[i] = p[i] ⊕ p[i-1]

Build prefix array: cpp vector<int> p(n + 1); p[0] = 0; for (int i = 1; i <= n; i++) { p[i] = (i == r) ? l - 1 : i; }

Recover original array: cpp for (int i = 1; i <= n; i++) { cout << (p[i] ^ p[i - 1]) << " "; }