| # | User | Rating |
|---|---|---|
| 1 | tourist | 3856 |
| 2 | jiangly | 3747 |
| 3 | orzdevinwang | 3706 |
| 4 | jqdai0815 | 3682 |
| 5 | ksun48 | 3591 |
| 6 | gamegame | 3477 |
| 7 | Benq | 3468 |
| 8 | Radewoosh | 3462 |
| 9 | ecnerwala | 3451 |
| 10 | heuristica | 3431 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 167 |
| 2 | -is-this-fft- | 162 |
| 3 | Dominater069 | 160 |
| 4 | Um_nik | 158 |
| 5 | atcoder_official | 156 |
| 6 | Qingyu | 154 |
| 7 | djm03178 | 152 |
| 7 | adamant | 152 |
| 9 | luogu_official | 150 |
| 10 | awoo | 147 |
Given an array A consist of N integers (N <= 100000, 0 <= Ai <= sqrt(i) for 1 <= i <= N). Count the number of triple (i, j, k) such that i <= j <= k and (Ai xor Aj xor Ak) = 0.
I tried many approaches but I couldn't optimize my O(N^2) solution. Is there any efficient algorithm to solve this problem?
We can improve complexity to
due to 
. Calculate frequencies of the elements while going from left to right, considering the Ak element in the triple. Now, we need to find the number of pairs i, j such that 
. Now, in 
time we can traverse the frequencies, considering element Aj, assuming 
, and adding freqAj × freqAi for Ai < Aj (that way we will count each pair once). Case of Ak = 0 should be handled separately — 
. The actual running time will be slightly better than 
since we don't traverse all the frequencies every iteration.