A5157 | $博弈$

时间限制1500ms

内存限制256MB

通过 / 提交0/0

题目描述

Alice 和 Bob 在进行一场博弈游戏，现在桌上有 $n$ 盘饼干，第 $i$ 盘饼干有 $a_i$ 个，他们两轮流取走饼干，Alice 先手。 在每个玩家的回合时，玩家将按顺序进行以下两个步骤： 1. 选择一个 非空 的盘子，从中取走正数个饼干。 2. 对于这盘中剩下的饼干，保持不动 或者 把这些饼干全部合并到另一个 非空 的盘子。 最终无法操作的人将输掉这场游戏。 现在，有 $q$ 次询问，每次会询问一个区间 $[l,r]$ ，请回答区间 $[l,r]$ 中有多少个子段 Alice 可以获胜。

第一行输入一个正整数 $n$ $(1\leq n\leq 2\times 10^5)$ ，表示盘子的数量。 第二行输入 $n$ 个正整数 $a_i$ $(1\leq a_i\leq 10^6)$ ，表示第 $i$ 个盘子中饼干的数量。 第三行输入一个正整数 $q$ $(1\leq q\leq 2\times 10^5)$ ，表示询问次数。 接下来 $q$ 行，每行输入两个正整数 $l,r$ $(1\leq l \leq r\leq n)$ ，表示查询的区间范围。

输出共 $q$ 行，对于每个询问，输出一个正整数表示询问区间中 Alice 可以获胜的子段个数。

输入 #1

输出 #1

C++ 编辑器

输入

输出