734. Triples Where Both Halves Agree

Count the triples of indices i < j <= k for which

a[i] ^ a[i+1] ^ ... ^ a[j-1] equals a[j] ^ a[j+1] ^ ... ^ a[k]

Indices are 0-based, and both halves must be non empty on the left and non empty on the right, which the strict i < j and the j <= k already ensure.

2 3 1 6 7 -> 4 1 1 1 1 1 -> 10 1 2 3 4 -> 2 1 -> 0

## j disappears from the condition

Write P for the prefix XOR, so the left half is P[j] ^ P[i] and the right half is P[k+1] ^ P[j]. Setting them equal:

P[j] ^ P[i] == P[k+1] ^ P[j]

XOR both sides by P[j]. It cancels on both sides at once, and the condition becomes

P[i] == P[k+1]

`j` is gone. The condition does not constrain the split point at all.

That is the entire problem. A brute force over three indices is O(n^3); realising that one of the three is unconstrained turns it into a count over pairs.

## Counting what is left

Given a pair i < k+1 with P[i] == P[k+1], every j strictly between i and k+1 works, and there are (k + 1) - i - 1 of them.

So the answer is, over every pair of positions in the prefix array holding the same value, the sum of their gaps minus one.

## Doing it in one pass

For each value, track how many times it has appeared and the SUM of those appearance indices. On meeting it again at position p:

contribution = count * (p - 1) - sumOfIndices

because each earlier index i contributes p - i - 1, and summing that over all of them is count * (p - 1) minus their total.

Recognising that a sum over pairs collapses into a running count and a running total is the second idea here, and it is what keeps the method linear rather than quadratic in the number of repeats.

## The empty prefix, for the third time

P[0] = 0 is a genuine position and must be in the tally before the sweep. It is what allows i = 0, which on 1 1 1 1 1 accounts for 4 of the 10 triples, so leaving it out still returns a plausible looking 6.

## Boundaries

A single value answers 0, since there is no room for two non-empty halves. Two equal values answer 1.

## Overflow

With every value equal the answer is on the order of n^3 / 6, which is about 10^15 at the limit. The running count * (p - 1) term reaches 4 * 10^10 on its own, so the tallies need 64 bits as well as the answer.

## What most people try first

Three nested loops over i, j and k, recomputing each half. That is O(n^3) before the XORs are even counted. The way out is not a faster loop but the observation below, that one of the three indices is not constrained at all.

## Cost

Time O(n). Space O(n).

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ each value ≤ 10^9`