Исключающее ИЛИ и динамического программирования

---

Этот вопрос был задан в ходе конкурса.Я предоставляю ссылку на вопрос.
Задачи программирования и конкурсы :: HackerRank[^]

В задаче в основном используются понятия теории игр и динамического программирования.

Что я уже пробовал:

Я знаю условие, чтобы выиграть игру nim, что нам нужно сделать.Таким образом, я мог расшифровать логику, но главная проблема заключалась в том, чтобы выяснить диапазоны, и я мог думать только о методе грубой силы. Затем я прочитал редакционную статью, и они использовали динамическое программирование, чтобы найти диапазоны. Я не мог понять соответствующей реализации. Пожалуйста, помогите.
Я вставляю как описание, так и код.
Если Алисе разрешено сделать свой особый ход, то она выигрывает тогда и только тогда, когда Боб проигрывает последующую игру Nim, сыгранную на стопках, которые Алиса не убрала.

Теперь, поскольку известно и может быть также доказано без особых усилий, что текущий игрок имеет выигрышную позицию в Nim тогда и только тогда, когда XOR размеров свай отличается от 0, Алиса выигрывает тогда и только тогда, когда она удаляет сваи в своем специальном движении таким образом, чтобы XOR размеров оставшихся свай был равен .
Отсюда следует, что если есть размеры всех свай, то Алиса выигрывает тогда и только тогда, когда она удаляет непрерывный диапазон свай таким образом, что a xor b xor c..=0 .
Прямой подход к подсчету количества таких диапазонов заключается просто в вычислении префикса и суффикса xor-сумм свай, а затем переборе всех возможных диапазонов, чтобы проверить, оставляет ли удаление такого диапазона сваи с XOR его размеров равными. Используя префикс и суффикс xor-суммы, можно выполнить одну такую проверку за O (1)времени. Однако этот подход имеет общую временную сложность, поскольку существует квадратичное число диапазонов для проверки.
Теперь они используют массив count для отслеживания диапазонов. Сначала они фиксируют левый конец диапазона. То, что мы хотим, - это xor чисел до l и после r(правый конец диапазона) =0.

Вот код.

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream> 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
#include <unordered_map>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)


typedef long long ll;
const int INF = 1e9;

const int N = 5e5;
const int V = 1e5;

int a[N+1];
int pref[N+1];

int main()
{
    int n;
    scanf("%d", &n);
    assert(n >= 1 && n <= N);
    REP(i, 1, n) {
        scanf("%d", &a[i]);
        assert(a[i] >= 1 && a[i] <= V);
    }
    pref[1] = a[1];
    REP(i, 2, n) {
        pref[i] = pref[i-1] ^ a[i];
    }

    ll res = 0;

    unordered_map<int, int> cnt;
    REP(i, 0, n-1) {
        if (cnt.find(pref[i]) == cnt.end()) {
            cnt[pref[i]] = 1;
        } else {
            cnt[pref[i]]++;
        }
    }
    int cur = 0;
    REPD(i, n-1, 0) {
        auto it = cnt.find(cur);
        if (it != cnt.end()) {
            res += it->se;
        }
        it = cnt.find(pref[i]);
        if (it != cnt.end()) {
            if (it->se > 1) {
                it->se--;
            } else {
                cnt.erase(it);
            }
        }
        cur ^= a[i+1];
    }
    printf("%lld\n", res);

    return 0;
}

---