Подотрезки с заданным XOR

1. Идея

Нужно посчитать количество подотрезков массива, XOR элементов которых равен k.

Перебирать все подотрезки напрямую нельзя: их O(n^2), а n до 2 * 10^5.

Ключевая идея — перейти от подотрезков к префиксным XOR.

Обозначим:

• pref[i] — XOR первых i элементов массива,
• pref[0] = 0.

Тогда XOR на подотрезке с границами l..r равен:

pref[r] ^ pref[l - 1]

Нам нужно, чтобы это значение было равно k, то есть:

pref[r] ^ pref[l - 1] = k

Отсюда:

pref[l - 1] = pref[r] ^ k

Значит, когда мы стоим в позиции r, нужно знать, сколько раз раньше встречался префиксный XOR, равный pref[r] ^ k.

Это удобно хранить в словаре: для каждого значения префиксного XOR запоминаем, сколько раз оно уже встретилось.

2. Наблюдения

Наблюдение 1. XOR подотрезка выражается через два префикса

Если pref — XOR префикса, то XOR элементов на подотрезке l..r:

a[l] ^ a[l+1] ^ ... ^ a[r] = pref[r] ^ pref[l-1]

Это полностью аналогично суммам через префиксные суммы, только вместо вычитания используется XOR.

Наблюдение 2. Для каждого правого конца можно быстро узнать число подходящих левых

Пусть текущий префиксный XOR равен pref.

Тогда нужно найти количество предыдущих префиксов со значением:

need = pref ^ k

Каждый такой префикс задаёт один подходящий подотрезок, заканчивающийся в текущей позиции.

Наблюдение 3. Начальное значение cnt[0] = 1 обязательно

Оно соответствует пустому префиксу до начала массива.

Это нужно, чтобы корректно считать подотрезки, начинающиеся с первого элемента.
Например, если XOR первых r элементов уже равен k, то должен учитываться подотрезок 1..r.

3. Алгоритм

1. Считываем n, k и массив.
2. Создаём словарь cnt, где:
   • ключ — значение префиксного XOR,
   • значение — сколько раз такой префикс уже встречался.
3. Изначально кладём cnt[0] = 1.
4. Идём по массиву слева направо:
   • обновляем текущий префиксный XOR: pref ^= a[i];
   • вычисляем need = pref ^ k;
   • прибавляем к ответу cnt[need], если такой ключ есть;
   • увеличиваем cnt[pref] на 1.
5. Выводим ответ.

4. Почему это работает

Докажем, что алгоритм считает ровно все подотрезки с XOR, равным k.

Пусть мы находимся в позиции r и уже посчитали текущий префиксный XOR pref[r].

Подотрезок l..r имеет XOR, равный k, тогда и только тогда, когда:

pref[r] ^ pref[l-1] = k

XOR обладает свойством обратимости, поэтому это равносильно:

pref[l-1] = pref[r] ^ k

Значит, число подходящих подотрезков, оканчивающихся в r, равно количеству таких индексов l-1, для которых значение префиксного XOR равно pref[r] ^ k.

Именно это количество и хранится в словаре cnt.

• Мы сначала узнаём, сколько подходящих префиксов уже было.
• Потом добавляем текущий префикс в словарь, чтобы он мог участвовать в подотрезках, заканчивающихся позже.

Таким образом:

• каждый подходящий подотрезок учитывается ровно один раз — когда рассматривается его правая граница;
• неподходящие подотрезки не учитываются, потому что для них не выполнено условие pref[l-1] = pref[r] ^ k.

Следовательно, алгоритм корректен.

5. Сложность

Для каждого элемента массива выполняется константное число операций со словарём.

• Время: O(n) в среднем.
• Память: O(n) в худшем случае, если все префиксные XOR различны.

6. Код на C++17

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    unordered_map<long long, long long> cnt;
    cnt[0] = 1;

    long long pref = 0;
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        pref ^= a[i];
        long long need = pref ^ k;
        if (cnt.find(need) != cnt.end()) {
            ans += cnt[need];
        }
        cnt[pref]++;
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

n, k = map(int, input().split())
a = list(map(int, input().split()))

cnt = {0: 1}
pref = 0
ans = 0

for x in a:
    pref ^= x
    need = pref ^ k
    ans += cnt.get(need, 0)
    cnt[pref] = cnt.get(pref, 0) + 1

print(ans)