K.Great Party

Solution

关键是需要推出一个结论：当堆数为奇数时有必胜策略。这样就只需要考虑偶数，偶数堆时谁让堆数-1谁就会输，因此将所有堆的石子数-1，就变成了nim博弈，那么本题就转化成了求区间内区间异或和不为0或长度为奇数的子区间个数，显然求区间内异或和为0的长度为偶数的子区间个数更方便，用莫队可以很容易离线求出所有答案。
时间复杂度$O(n\sqrt{n})O(n\backslash sqrt\{n\})$。

int sum[2][1 << 20], pre[N], blo, bel[N];
ll ans[N];
struct Node {
    int id, l, r;
    bool operator <(const Node s)const { return bel[l] < bel[s.l] || (bel[l] == bel[s.l] && r < s.r); }
}q[N];

int main() {
    int n = fast_IO::read(), m = fast_IO::read();
    for (int i = 1; i <= n; ++i)pre[i] = pre[i - 1] ^ (fast_IO::read() - 1);
    blo = sqrt(n);
    for (int i = 1; i <= n; ++i)bel[i] = (i - 1) / blo + 1;
    for (int i = 1; i <= m; ++i) {
        q[i].l = fast_IO::read() - 1;
        q[i].r = fast_IO::read();
        q[i].id = i;
    }
    sort(q + 1, q + m + 1);
    int l = 0, r = 0;
    ll now = 0;
    sum[0][0] = 1;
    for (int i = 1; i <= m; ++i) {
        while (r < q[i].r) {
            ++r;
            now += sum[r & 1][pre[r]]++;
        }
        while (r > q[i].r) {
            now -= --sum[r & 1][pre[r]];
            --r;
        }
        while (l < q[i].l) {
            now -= --sum[l & 1][pre[l]];
            ++l;
        }
        while (l > q[i].l) {
            --l;
            now += sum[l & 1][pre[l]]++;
        }
        ans[q[i].id] = (ll)(r - l) * (r - l + 1) / 2 - now;
    }
    for (int i = 1; i <= m; ++i)
        printf("%lld\n", ans[i]);
    return 0;
}