First One

这道题是一道非常经典的**“枚举贡献 + 双指针”**问题。

核心难点在于公式中含有 $\lfloor \log_2 S(i, j) \rfloor$。直接枚举所有子区间 $(i, j)$ 的复杂度是 $O(n^2)$，对于 $n=10^5$ 的数据规模会超时。我们需要利用对数的性质和双指针将复杂度降下来。

1. 核心思路

第一步：转换视角（按 Log 值分层） 由于 $S(i, j)$ 最大为 $10^5 \times 10^5 = 10^{10}$，而 $\log_2(10^{10}) \approx 33$。 这就意味着，$\lfloor \log_2 S(i, j) \rfloor$ 的取值范围非常小（只有 0 到 34 左右）。

我们可以遍历这个对数值 $k$（从 0 到 35）。对于每一个固定的 $k$，我们需要找到所有的子区间 $(i, j)$，满足：

这等价于区间和 $S(i, j)$ 落在以下范围内：

特殊情况处理：题目规定 $\log_2 0 = 0$。 当 $k=0$ 时，$\lfloor \log_2 S \rfloor = 0$，对应的公式值为 1。此时 $S$ 的范围不仅包括 $[2^0, 2^1) = [1, 2)$，还应该包括 $0$。 所以我们修正一下区间的定义：

• 当 $k=0$ 时，目标区间和范围是 $[0, 2)$。
• 当 $k > 0$ 时，目标区间和范围是 $[2^k, 2^{k+1})$。

第二步：使用双指针固定区间 对于一个固定的 $k$，我们有一个目标和的范围 $[L_{bound}, R_{bound})$。 我们需要对于每一个起点 $i$，找到满足条件的终点 $j$ 的范围。 假设前缀和数组为 $P$，则 $S(i, j) = P[j] - P[i-1]$。 我们需要找到 $j$，使得：

由于数组元素非负，$P[j]$ 是单调不减的。 对于固定的 $i$，随着 $i$ 的增加，$P[i-1]$ 变大，需要满足条件的 $P[j]$ 也变大，因此合法的 $j$ 的位置只会向右移动（或不动），不会回退。 这正是**双指针（滑动窗口）**的应用场景。

我们需要维护两个指针（假设为 idx1 和 idx2）：

1. idx1: 满足 $P[idx1] \ge P[i-1] + L_{bound}$ 的最小下标。
2. idx2: 满足 $P[idx2] \ge P[i-1] + R_{bound}$ 的最小下标。

那么对于当前的 $i$，合法的 $j$ 的范围就是 $[idx1, idx2 - 1]$。 这一段区间内的每一个 $j$，它们对答案的贡献权重都是 $(k+1)$，它们贡献的值是 $(i+j)$。

第三步：数学求和 对于范围 $j \in [l, r]$，我们需要计算 $\sum (i + j)$：

2. 复杂度分析

• 外层循环枚举 $k$：大约 35 次。
• 内层双指针扫描整个数组：$O(n)$。
• 总时间复杂度：$O(35 \times n)$，对于 $10^5$ 的数据量，运算次数约 $3.5 \times 10^6$，完全可以在 1 秒内通过。

3. C++ 代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

        #include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 100005;
ll a[MAXN];
ll P[MAXN]; // 前缀和

void solve() {
    int n;
    if (!(cin >> n)) return;
    
    P[0] = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        P[i] = P[i-1] + a[i];
    }

    ll total_ans = 0;

    // 枚举 k，即 log2(S(i,j)) 的值
    // S 的最大值是 10^10，log2(10^10) ≈ 33.2，枚举到 36 足够
    for (int k = 0; k <= 36; ++k) {
        // 计算当前 k 对应的区间和范围 [lower, upper)
        ll lower, upper;
        if (k == 0) {
            lower = 0; // 特殊处理 log2(0)=0 的情况
            upper = 2;
        } else {
            lower = (1LL << k);
            upper = (1LL << (k + 1));
        }

        // 双指针寻找合法的 j 区间 [l, r-1]
        // l: 第一个满足 sum >= lower 的位置
        // r: 第一个满足 sum >= upper 的位置
        // 合法区间即为 sum 在 [lower, upper) 之间
        int l = 1, r = 1;
        
        for (int i = 1; i <= n; ++i) {
            // 确保 l 和 r 不小于当前起点 i
            if (l < i) l = i;
            if (r < i) r = i;

            // 移动 l 指针，直到 P[l] - P[i-1] >= lower
            while (l <= n && P[l] - P[i-1] < lower) {
                l++;
            }

            // 移动 r 指针，直到 P[r] - P[i-1] >= upper
            while (r <= n && P[r] - P[i-1] < upper) {
                r++;
            }

            // 此时合法的 j 的范围是 [l, r - 1]
            // 如果 l >= r，说明不存在合法的 j
            if (l < r) {
                // 计算区间 [l, r-1] 内有多少个 j
                ll count = (r - 1) - l + 1;
                
                // 计算区间内所有 (i + j) 的和
                // sum = i * count + (l + (r-1)) * count / 2
                ll sum_ij = i * count + (ll)(l + (r - 1)) * count / 2;
                
                // 累加到总答案：(log值 + 1) * sum_ij
                // 这里的 log值 就是 k (或者 k=0 时对应公式里的值也是1，即 k+1)
                total_ans += (ll)(k + 1) * sum_ij;
            }
        }
    }

    cout << total_ans << endl;
}

int main() {
    // 优化 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

    

代码细节解释：

1. 区间范围 (lower, upper)：

   • 题目公式是 floor(log2(sum)) + 1。
   • 如果 sum 在 $[2^k, 2^{k+1})$ 之间，floor(log2) 是 $k$，公式值是 $k+1$。
   • 特别地，如果 sum=0，题目说视为 log2(0)=0，公式值是 $1$。如果 sum=1，log2(1)=0，公式值也是 $1$。所以 $k=0$ 时我们将范围设为 $[0, 2)$，权重为 $1$，逻辑是统一的。

2. 双指针逻辑：

   • 我们使用两个 while 循环分别寻找区间的左边界 l 和右边界 r。
   • l 是第一个达标的（大于等于下界）。
   • r 是第一个超标的（大于等于上界）。
   • 所以有效的 $j$ 是从 l 到 r-1。

3. 等差数列求和：

   • 我们需要求 $\sum_{j=l}^{r-1} (i + j)$。
   • 拆开来看就是 $\sum i + \sum j$。
   • $\sum i$ 就是 $i \times \text{count}$。
   • $\sum j$ 是从 $l$ 加到 $r-1$，直接用首项加末项乘以项数除以2。

理解

利用双指针在 $O(n)$ 时间内找到 “区间和落在特定范围内 $[L, R)$” 的所有区间。

这就是解题的“灵魂”所在。

这里有三个核心要素支撑着这个算法的正确性和高效性：

1. 核心变换：化“变量”为“常量”

原题的难点在于 $\lfloor \log_2 S(i, j) \rfloor$ 是随区间变化的。 我们通过 枚举 $k$（0 到 35），把这个变化的 Log 值固定下来。 这就把原问题转化成了 35 个独立的子问题：

在数组中寻找所有满足 $2^k \le S(i, j) < 2^{k+1}$ 的子区间。

2. 核心性质：单调性（非负整数）

双指针能跑 $O(n)$ 的前提是 数组元素非负（$a_i \ge 0$）。

• 当我们固定左端点 $i$，向右移动寻找 $j$ 时，区间和是单调递增的。
• 当我们把左端点 $i$ 向右移一格（$i \to i+1$），区间和变小了。为了让和重新回到 $[2^k, 2^{k+1})$ 这个目标范围，右端的指针 $j$ 只能向右移，绝不需要回头。

正是因为 “右指针不回头” 这一特性，保证了对于每一个 $k$，扫描一遍数组的复杂度是严格的 $O(n)$。

3. 核心技巧：批量处理

如果不使用双指针，固定 $i$ 后二分查找 $j$，复杂度是 $O(n \log n)$，总复杂度会变成 $O(35 \cdot n \log n)$，可能会比较慢。 而双指针利用了 $i$ 和 $j$ 的联动关系，直接把二分的那个 $\log n$ 给消掉了，变成了线性的 $O(n)$。

总结

你的直觉很准： 这道题就是把 “求解 Log 值的和” 拆解成了 35 次“定值范围的区间查找”，然后用 双指针 这一武器对每次查找进行 $O(n)$ 级别的秒杀。