从CF1879D学习一类区间贡献题思路

https://codeforces.com/contest/1879/problem/D

关键在于互换两个 (\sum)​ 的顺序

一般像这样计算所有子区间的式子，如果要优化成接近线性，有一种可行思路是把注意力放在右端点，通过不断移动右端点，在移动的时候利用前面的统计结果算出移动右端点后的结果，从而得出所有子区间的答案。然后还有一个显然有用的套路是前缀和，这里记 $s_i=a_1 \oplus a_2\oplus ···\oplus a_{n-1}\oplus a_n $ ，(s_{i,j}) 为 (s_i) 二进制的第 (j) 位，我们会发现 (\sum_{l=1}{n}\sum_{r=l}{n}f(l,r)=\sum_{i=0}{32}\sum_{l=1}{n}\sum_{r=l}^{n}s_{l,i} \oplus s_{r,i}\times 2^i)

由于上面的式子可以优化成 (O(n\operatorname{log}V))，我们受到启发推出下面的式子

(\sum_{l=1}{n}\sum_{r=l}{n}f(l,r)\times(r-l+1))

(=\sum_{r=1}{n}\sum_{l=1}{r}f(l,r)\times(r-l+1)(调换∑位置))

(=\sum_{r=1}{n}\sum_{l=1}{r}\sum_{i=0}^{32} s_{l,i} \oplus s_{r,i}\times 2^i\times(r-l+1))

(=\sum_{r=1}{n}\sum_{i=0}{32} \sum_{l=1}^{r}[ s_{r,i}\oplus s_{l,i} =1]\times 2^i\times(r-l+1))

(=\sum_{r=1}{n}\sum_{i=0}{32} 2i\times\sum_{l=1}{r}([ s_{r,i}\oplus s_{l,i} =1]\times r-[ s_{r,i}\oplus s_{l,i} =1] \times (l-1)))

把 (r)​ 视作常量再观察上面的式子，你就会发现最后一维可以被优化掉，因为 $\displaystyle \sum_{l=1}^{r}[ s_{r,i}\oplus s_{l,i} =1]\times r $​ 和 (\displaystyle \sum_{l=1}^{r}[ s_{r,i}\oplus s_{l,i} =1]\times (l-1))​ 都可以预处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve()
{
// #define tests
    int n; std::cin >> n;
    std::vector<int> a(n); for (auto& x : a) {std::cin >> x;}
    PrefixXor<i64> pre_xor(a);
    
    std::vector cnt(2, std::vector<Z>(31));
    auto sum(cnt);//维护该数之前该位上为0/1的个数
    cnt[0].assign(31, 1);//一开始0的个数赋成1
    Z ans = 0;
    for (int r = 1; r <= n; r++) {//固定r，更新答案
        for (int j = 30; j >= 0; j--) {
            int x = (pre_xor(r) >> j & 1);
            ans += (cnt[x ^ 1][j] * r - sum[x ^ 1][j]) * (1 << j);//找当前位相反的数码的数量，只用这样才能产生贡献，即异或和为 1
            sum[x][j] += r; cnt[x][j] += 1;
        }
    }
    std::cout << ans << '\n';
}