这绝对是一个非常好的题，中午去吃一顿饭的功夫就想出来这个小巧思。

思路

首先我们考虑按位或的性质。

假设有一个 0/1 数组。由性质得，如果一个区间只要存在 1，那么这个区间的贡献就是 1。定义 $f_i$ 表示以 $i$ 结尾的所有区间的贡献和，所以 $f_i$ 显然就是间 $[1,i]$ 中最后一个 1 出现的位置，答案就是 $\sum f_i$。回到原题，我们会很容易想到把每一个数拆位来计算贡献，对于每一位，从头到尾跑一遍。注意其实 $a_i$ 和 $f_i$ 其实没必要存下来，就可以省下来空间。时间复杂度 $O(n \log V)$，会拿到 30pts 的好成绩。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace READ;
int lst[70];
ull ans;
void solve() {
    int n;
    init(n);
    for (int i = 1; i <= n; i++) {
        ull x = read();
        // Brute Force
        for (int b = 0; b < 64; b++) {
            if ((x >> b) & 1) lst[b] = i;
            ans += (1ll << b) * lst[b];
        }
    }
    cout << ans << endl;
}

我们考虑优化。首先定义 $l_i$ 表示当前位置第 $i$ 个数位最后一个 1 出现的位置，那么对于当前这个位置的答案就是 $\sum 2^i \times lst_i$。我们发现拆数位比拆位置的位数多很多，那我们为什么不拆位置呢？所以我们定义 $c_i$ 表示位置二进制拆分后第 $i$ 位为 1 的每一个数位是否存在最后一个 1 的情况。我们发现按照状压的方法存，$c_i$ 天然地帮我们乘好了每一个数位的系数。最终这个位置的答案就是 $\sum 2^i \times c_i$（注意这里的 $i$ 表示拆分的位置，而不是数位）。

我们考虑怎么维护 $c_i$？过程可以分成两步，一步是删去新加数的数位上原来的贡献，一步是加上现在的贡献。假设当前位置上的值是 $x$，第一步给每一个 $c_i$ 执行 $c_i \leftarrow c_i \land \overline{x}$，第二步对于拆分位置后是 1 的 $c_i$ 执行 $c_i \leftarrow c_i \lor x$，最后把答案合并算一下就行了。满分代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace READ;
ull cnt[30], ans;
void solve() {
    int n, l = 0;
    init(n);
    for (int i = 0; i < n; i++) {
        ull x = read();
        for (int b = 0; b <= l; b++) cnt[b] &= (~x);
        for (int b = 0; b <= l; b++) cnt[b] += x * ((i + 1 >> b) & 1);
        for (int b = 0; b <= l; b++) ans += cnt[b] * (1 << b);
        l += ((i & -i) == i); 
    }
    cout << ans << endl;
}

时间复杂度 $O(n \log n)$，这个数据范围虽然看着十分恐怖，但是实际上只需要 1s 左右，跑得飞快。