AT_abc365_e 题解

Vitamin_B · 2024-08-08 12:39:57 · 题解

思路

按位拆解求答案。若 r 二进制第 j 位为 1，则 r 之前的第 j 位全部反转，即变为 r-s_j\to s_j 有贡献了。最后注意把答案减去 \sum a_i，因为要求 l<r。

代码

# include <bits/stdc++.h>
# define I return
# define AK 0
# define IOI ;
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
int n, x, s[35];
ll sum;
int main () {
    ios::sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> x, sum -= x;
        for (int j = 0; j < 30; ++ j) {
            if (x >> j & 1)
                s[j] = i - s[j];
            sum += ((ll) s[j]) << j;
        }
    }
    cout << sum;
    I AK IOI
}