This might be a weird question to ask here , i don’t know the rules , but can anyone explain [https://www.codechef.com/viewsolution/25520022] (https://www.codechef.com/viewsolution/25520022) this solution

# Explain a Solution!

It’s hard to decipher, but at first glance it doesn’t *appear* to be doing anything fundamentally different to the other solutions.

Lots of people are posting solutions and descriptions of approach here, so maybe that’s worth a read

i sorted the solution according to time then i got this one at top , though mine also got accepted(after a lot hard work ) in 0.11 seconds but this seem more optimized like only in 0.06 seconds

Basically, the answer is \sum\limits_{i} (len_{i} - 1) for all the intervals that have XOR sum equal to 0 (since every i \leq k \leq j of these intervals holds the equal XOR sum condition, but we can’t take k = i, so we will have len_{i}-1 for each one), so if we handle it like prefix sums, we would have:

prefix[i] = XOR(a_{1},\ldots,a_{i}) \rightarrow XOR(a_{i},\ldots,a_{j}) = XOR(prefix[j],prefix[i-1])

Also, let’s define prefix[0] = 0 to be able to consider the whole prefix until a certain index.

So, to count the number of intervals that have XOR sum equal to 0 that end in index R, we need all the i such that 0 \leq i < R and prefix[i] = prefix[R]. However, each i defines the interval (i+1,R) so the length of this segment is R - i. Thus, R contributes with:

contribution(R) = \sum\limits_{0 \leq i < R, prefix[i] = prefix[R]} (R - i) - 1

contribution(R) = \sum\limits_{0 \leq i < R, prefix[i] = prefix[R]} R - (i + 1)

contribution(R) = Q(0,R-1,prefix[R])\cdot R - \sum\limits_{0 \leq i < R, prefix[i] = prefix[R]}(i + 1)

Where Q(L,R,x) are the number of indices L \leq i \leq R such that prefix[i] = x.

If we mantain the sum of (i+1) for each value of prefix[i] = val in sm[val] and the number of such indices that hold in sz[val], we can transform the complete sum into:

contribution(R) = sz[prefix[R]]\cdot R - sm[prefix[R]]

That’s all the idea behind the solution

It is hard to understand what the Code does , it is much harder to understand why ?