小苯的美丽区间

[牛客链接](https://www.nowcoder.com/practice/b80c412275d44f2c8312cfedaa630faa)

题意

一个正整数 $x$ 是「美丽数」当且仅当它是 $2$ 的幂次。美丽值定义为 $\log_2 x$ （即不断除以 $2$ 的次数），非美丽数的美丽值为 $0$ 。

给定长度为 $n$ 的正整数数组 $a$ ，求所有连续子数组之和的美丽值之和。

思路

枚举 $2$ 的幂次 + 前缀和哈希

暴力枚举所有子数组是 $O(n^2)$ ，但注意到一个子数组和 $S$ 只有在 $S = 2^k$ 时才有贡献 $k$ ，而 $2^k$ 的取值只有 $O(\log(\text{sum}))$ 种（ $\text{sum}$ 为数组总和），这就为我们打开了突破口。

核心思路：把"枚举子数组"转化为"枚举目标值"。

设前缀和 $p_0 = 0,\; p_j = \sum_{i=1}^{j} a_i$ 。子数组 $[i+1, j]$ 的和为 $p_j - p_i$ 。对于固定的 $k$ ，我们要统计满足 $p_j - p_i = 2^k$ 的有序对 $(i, j)$ （ $0 \le i < j \le n$ ）的个数，然后乘以 $k$ 计入答案。

这就是经典的「两数之差为定值」问题——从左到右扫描 $p_j$ ，用哈希表记录之前出现过的前缀和及其次数，每次查找 $p_j - 2^k$ 是否在表中即可。

时间分析： $k$ 最多到 $\lfloor\log_2(\text{sum})\rfloor$ ，每轮 $O(n)$ ，总计 $O(n \log \text{sum})$ 。由于 $\sum n \le 10^5$ ，完全够用。

以样例 $\{2,2,2,2\}$ 验证：前缀和为 $[0,2,4,6,8]$ 。

$k=1, 2^1=2$ ：差为 $2$ 的对有 $(0,2),(2,4),(4,6),(6,8)$ ，共 $4$ 对，贡献 $1 \times 4 = 4$ 。
$k=2, 2^2=4$ ：差为 $4$ 的对有 $(0,4),(2,6),(4,8)$ ，共 $3$ 对，贡献 $2 \times 3 = 6$ 。
$k=3, 2^3=8$ ：差为 $8$ 的对有 $(0,8)$ ，共 $1$ 对，贡献 $3 \times 1 = 3$ 。

总计 $4 + 6 + 3 = 13$ ，与预期一致。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<long long> a(n);
        long long total = 0;
        for (int i = 0; i < n; i++) {
            scanf("%lld", &a[i]);
            total += a[i];
        }

        long long ans = 0;
        for (int k = 0; (1LL << k) <= total; k++) {
            long long pw = 1LL << k;
            unordered_map<long long, int> cnt;
            cnt.reserve(n + 1);
            long long prefix = 0;
            cnt[0] = 1;
            for (int i = 0; i < n; i++) {
                prefix += a[i];
                auto it = cnt.find(prefix - pw);
                if (it != cnt.end()) {
                    ans += (long long)k * it->second;
                }
                cnt[prefix]++;
            }
        }

        printf("%lld\n", ans);
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            long[] a = new long[n];
            long total = 0;
            for (int i = 0; i < n; i++) {
                a[i] = Long.parseLong(st.nextToken());
                total += a[i];
            }

            long ans = 0;
            for (int k = 0; (1L << k) <= total; k++) {
                long pw = 1L << k;
                HashMap<Long, Integer> cnt = new HashMap<>();
                cnt.put(0L, 1);
                long prefix = 0;
                for (int i = 0; i < n; i++) {
                    prefix += a[i];
                    Integer c = cnt.get(prefix - pw);
                    if (c != null) {
                        ans += (long) k * c;
                    }
                    cnt.merge(prefix, 1, Integer::sum);
                }
            }

            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
}

复杂度分析

时间复杂度： $O(n \log S)$ ，其中 $S = \sum a_i$ 为数组总和。外层枚举 $O(\log S)$ 个幂次，内层每次 $O(n)$ 哈希扫描。
空间复杂度： $O(n)$ ，哈希表存储前缀和。