First One

暴力

3分钟写个暴力,验证一下有没有读错题目

        
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

        #include <bits/stdc++.h>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 1e5+6;
ll a[maxn];
int n;

ll range_sum(int l,int r){ return a[r] - a[l-1]; }

void init() {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
        a[i] += a[i-1]; //前缀和
    }
}

ll log2(int l,int r) {
    ll sum = range_sum(l, r);
    return log(sum)/ log(2);
}

ll baoli() {
    ll ret = 0;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        for(int j = i;j <= n ;++j ) // j: 1->n
        {
            ret += (log2(i,j)+1) * (i+j);
        }
    }
    return ret;
}

int main (int argc, char *argv[]) {
    int T;
    std::cin >> T;
    while (T--) {
        init();
        cout << baoli() << endl;
        
    }
    
    return 0;
}

    

思考

根据公式, 必须要枚举区间$[i,j]$,枚举的时间$O(n^2)$,怎么不枚举呢?

发现: 不是让直接求区间和,而是求$log_2^{S(i,j)}$, 注意到: 而log的结果很少的,

第一步：转换视角（按 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$。 当 $S=0$ 时，$\lfloor \log_2 S \rfloor = 0$，

这说明当我们枚举区间和为 $S = 0$ 时,那么对应得到的$log_2S = 0$

对应的公式值为 1。此时 $S$ 的范围不仅包括 $[2^0, 2^1) = [1, 2)$，还应该包括 $0$。

• $2^0 = 1 \leqslant S(i,j) < 2 \to k \in [0,1)$, 可以知道,当我们规定$k = 1$时,我枚举的$S(i,j) \in [0,2)$
• $\leqslant S(i,j) = 0 \to log$

所以综上,所以我们修正一下区间的定义：

• 当 $S=0$ 时，目标区间和是 $0$,此时得到$k=log_2S = 0$
• 当 $2^0 \leqslant S < 2^1$ 时，目标区间和是 $1$,此时得到$k=log_2S = 0$
• 结合上两条: $0 \leqslant S < 2^1$,此时得到的$k = 0$
• 当 $2^k \leqslant S < 2^{k+1}$ 时，目标区间和是 $1$,此时得到$k=log_2S = k$

我们在把原数组a 转成前缀和数组$P$, 针对某个$k$,我要求的就是,有多少对$(i,idx)$,满足$2^k \leqslant P[idx] - P[i] < 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

        // 发现 ai >=0, 那么可以不用前缀和数组
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 1e5+6;
ll a[maxn]; // 前缀和
ll P[maxn]; // 前缀和
int n;

void init() {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
        P[i] = a[i] +P[i-1]; 
    }
}

ll sum(int l,int r) {
    return P[r] - P[l-1];
}

void  work() {
    ll ans = 0;

    for(int k = 0;k<=34;k++) {

        // 坑点
        ll lower_bound = (1ull << ll(k));
        if( k == 0) lower_bound = 0;
        ll up_bound = (1ull << ll(k+1) );

        ll j1 = 0,j2 = 0;
        // 枚举起点
        for(ll i = 1 ; i <=  n;i++) {
            j1 = std::max(j1,i);

            // ll sum = P[j1].val - P[i].val;
            // 第一个 sum >= lower_bound的位置
            while(sum(i,j1) < lower_bound && j1 <=n) j1++; 
                
            j2 = std::max(j2,j1);
            // 第以个 sum >= up_bound的位置
            while(sum(i,j2) < up_bound && j2 <=n ) j2++;

            // 没有超过边界
            if( j1 <= n) {
                // cout << "k = " << k << " " ;
                // cout << "i = "  << i << ' ';
                // cout << "j1 = " << j1 << ' ';
                // cout << "j2 = " << j2 << ' ';
                ll ij_plus_sum = i * (j2 - j1) + (j2-1+j1) * (j2-j1) / 2;
                ll sum_k =  (k+1) * ij_plus_sum;
                // cout 
                ans += sum_k;
                // cout << "sum_k = " << sum_k << " \n";
            }
        }

    }


    std::cout << ans << "\n";
}

int main (int argc, char *argv[]) {
    int T;
    std::cin >> T;
    while (T--) {
        init();
        work();
    }
    
    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)$ 级别的秒杀。