题意简化

数组 $a_1..a_n$，每次询问区间 $[l, r]$，求有多少子区间 $[x, y]$ 满足：

1. $l \le x \le y \le r$
2. 从 $x$ 开始的异或前缀序列单调不下降

即：设 $s_i = a_x \oplus a_{x+1} \oplus \dots \oplus a_i$，要求 $s_x \le s_{x+1} \le \dots \le s_y$。

代码核心思路

1. 预处理关键信息

pre[i] = pre[i-1] ^ a[i];  // 前缀异或

2. 单调性条件分析

代码中的 c(x, m) 函数判断：从位置 $x$ 开始，能否延伸到位置 $m$（即区间 $[x, m]$ 是否满足单调性）。

关键定理：$s_i \le s_{i+1}$ 等价于： 设 $h = \text{最高位}(a_{i+1})$，则 $pre_{i-1}$ 的第 $h$ 位必须等于 $pre_i$ 的第 $h$ 位。

证明：

• $s_i = pre_i \oplus pre_{x-1}$
• $s_{i+1} = pre_{i+1} \oplus pre_{x-1}$
• 单调条件 ⇒ $(pre_i \oplus pre_{x-1})$ 的第 $h$ 位必须为 $0$

3. 前缀计数数组

f[0][i][h] 和 f[1][i][h] 记录：

• 前 $i$ 个位置中，$pre_j$ 的第 $h$ 位为 $0$ 的次数
• 前 $i$ 个位置中，$pre_j$ 的第 $h$ 位为 $1$ 的次数

用于快速判断条件。

4. 计算每个起点的最远延伸

对于每个起点 $i$，二分查找最大的 $rig[i]$，使得区间 $[i, rig[i]]$ 满足单调性。

c(i, m) 检查：

• 对于所有位 $h$，检查是否有违反条件的情况
• 即：$pre_{i-1}$ 的某位如果是 $1$，则 $f[0][m][h] - f[0][i-1][h]$ 必须为 $0$（没有中间位置的该位为 $0$）
• 反之亦然

5. 主席树优化查询

对于询问 $[l, r]$，需要计算：

$$\sum_{x=l}^{r} \min(rig[x], r) - x + 1$$

这等价于：对于每个 $x \in [l, r]$，数轴区间 $[x, rig[x]]$ 与 $[l, r]$ 的交集长度求和。

主席树维护：

• 版本 $i$：包含所有起点 $\le i$ 的区间 $[x, rig[x]]$
• 查询：$rt[r]$ 与 $rt[l-1]$ 的差，统计覆盖区间 $[l, r]$ 的部分

算法步骤

1. 输入预处理

   • 计算前缀异或 $pre[i]$
   • 计算每个数的最高位 $g(a_i)$

2. 构建计数数组

   • f[0/1][i][h] 前缀和

3. 计算 $rig[i]$

   • 对每个 $i$ 二分
   • 用 c(i, m) 检查单调性

4. 构建主席树

   • 对每个 $i$，将区间 $[i, rig[i]]$ 插入主席树版本 $i$

5. 回答询问

   • 计算真正的 $l, r$（强制在线）
   • 查询主席树：区间 $[l, r]$ 内有多少点被起点在 $[l, r]$ 的区间覆盖

复杂度分析

• 预处理 $f$ 数组：$O(31n)$
• 计算 $rig[i]$：二分 $O(\log n)$，检查 $O(31)$，总 $O(31n \log n)$
• 主席树：$O(n \log n)$ 建树，$O(\log n)$ 查询
• 总复杂度可过 $n=10^5$

关键优化

1. 单调性判定

将复杂的异或单调条件转化为位运算检查，用前缀计数数组 $O(1)$ 判断。

2. 二分延伸

对每个起点二分找最远延伸点，避免 $O(n^2)$。

3. 主席树统计

将区间求和问题转化为二维数点，用主席树高效查询。

样例解释

输入：

4
1 2 3 4

• $a = [1,2,3,4]$
• $pre = [1,3,0,4]$

计算 $rig$：

• $rig[1]=2$：区间[1,2]满足
• $rig[2]=2$：区间[2,2]满足
• $rig[3]=4$：区间[3,4]满足
• $rig[4]=4$：区间[4,4]满足

询问 $[1,3]$：

• 起点1：贡献区间[1,2]与[1,3]交集长度2
• 起点2：贡献区间[2,2]与[1,3]交集长度1
• 起点3：贡献区间[3,4]与[1,3]交集长度1 总和：4

代码特点

• 位运算优化
• 二分+前缀检查
• 主席树维护区间覆盖
• 强制在线处理