解题思路

1. 定义纯净度：对于非负整数 $x$，若存在非负整数 $k$ 使得 $x = 2^k$，则纯净度 $g(x) = k$；否则 $g(x) = 0$。特别地，当 $x = 1 = 2^0$ 时纯净度为 $0$。
2. 前缀和转换：设前缀和数组 $P$，其中 $P[0] = 0$，$P[i] = \sum_{j=1}^{i} a_j$。任意子数组 $[l, r]$ 的和可以表示为 $S = P[r] - P[l-1]$。因此，问题转化为统计所有满足 $P[r] - P[l-1] = 2^k$ 的前缀对 $(l-1, r)$ 的贡献，贡献值为 $k$（$k \ge 1$ 时有效，$k=0$ 时贡献为 $0$）。
3. 哈希表优化：固定右端点 $r$，维护一个哈希表（字典）记录所有已出现的前缀和 $P[l-1]$ 及其出现次数。对于当前前缀和 $P[r]$，枚举可能的 $k$ 值，计算目标值 $\text{target} = P[r] - 2^k$，若该 target 在哈希表中存在，则答案增加 $k \times \text{freq}[\text{target}]$。枚举 $k$ 的上限由前缀和的上限决定：数组元素最大 $<2^{30}$，长度最大 $3\times 10^5$，前缀和上限在 $2^{60}$ 以内，枚举 $k$ 从 $1$ 到 $60$ 已完全足够。
4. 边界处理：初始时前缀和 $0$ 已出现一次（对应 $l=1$ 时 $l-1=0$ 的情况）。
5. 输出：对于每组数据输出答案，答案可能较大，需使用 64 位整数（long long / int64）。

复杂度分析