题解：[ABC384F] Double Sum 2

· · 题解

看题解区似乎都是好多神奇做法我看不懂，我直接正着做。

首先按照 \operatorname{lowbit} 从小到大排序，假设我们当前考虑到位置 a_i，前面的某个数为 a_j(j<i)。

若他们 \operatorname{lowbit}(a_j)>\operatorname{lowbit}(a_i)，则 \operatorname{lowbit}(a_i+a_j) 必定等于 \operatorname{lowbit}(a_i)。这很好维护。重点在于 \operatorname{lowbit}(a_j)=\operatorname{lowbit}(a_i) 的情况。

假设现在有两个数 101100 110100，他们的 \operatorname{lowbit} 是相等的，于是我们考虑 \operatorname{lowbit} 后面的部分，看有没有可能产生更多的末尾 0。容易发现只要从 \operatorname{lowbit} 后一位开始从低到高若他们的每一位一直都是不一样的，那么可以一直产生 0。

如刚刚的两个数，他们的和是 1100000, 在从低到高第 5 位出现了 1，这也是他们从 \operatorname{lowbit} 开始第一个一样的地方。

有点最大异或和那味了，发现这东西可以用 trie 树维护。

当然还有一些细节处理一下就完了。时间复杂度 O(n\log V)，最慢点 276 ms。

trie 需要开到 9\times10^6。

附上马蜂不优良 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node {
    ll sum, cnt, s0, s1;
}trie[9000002];
ll n, a[200002], ans, r, idx, now;
ll lowbit(ll x) {
    if (! x) return 114514;
    return x & (-x);
}
bool cmp(ll az, ll bz) {
    return lowbit(az) > lowbit(bz); 
}
ll s0(ll x) {
    if (! trie[x].s0) trie[x].s0 = ++ idx;
    return trie[x].s0;
}
ll s1(ll x) {
    if (! trie[x].s1) trie[x].s1 = ++ idx;
    return trie[x].s1; 
} 
ll fd(ll x, ll p, ll d) {
    if (d > 30) return 0; 
    if (x & (1 << d)) return ((trie[s1(p)].sum + trie[s1(p)].cnt * now) >> d) + fd(x, s0(p), d + 1);
    return ((trie[s0(p)].sum + trie[s0(p)].cnt * now) >> d) + fd(x, s1(p), d + 1);
}
void update(ll x, ll p, ll d) {
    if (d > 30) return;
    if (d > 1) trie[p].sum += x, trie[p].cnt ++;
    if (x & (1 << d)) update(x, s1(p), d + 1);
    else update(x, s0(p), d + 1);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i ++ ) cin >> a[i];
    sort(a + 1, a + n + 1, cmp);
    for (ll i = 1, sum1 = 0, cnt1 = 0, sum2 = 0, cnt2 = 0; i <= n; i ++ ) {
        ans += (sum1 + cnt1 * a[i]) / lowbit(a[i]);
        cnt2 ++, sum2 += a[i]; 
        now = a[i] / lowbit(a[i]);
        update(now, r, 1);
        ans += fd(now, r, 1);
        if (lowbit(a[i]) != lowbit(a[i + 1])) cnt1 += cnt2, sum1 += sum2, cnt2 = 0, sum2 = 0, r = ++ idx;
    }
    cout << ans;
}