P3760 [TJOI2017] 异或和 简单的单 log 做法

· · 题解

一个简单的 O((n+V)\log V) 做法。

推荐一个类似题：gym 102538E，处理技巧一致。

区间和问题，在前缀和上考虑。异或问题，每一位分开考虑。

对于前缀和 s_i，考虑哪些前缀和会和它在第 bit 位产生贡献：可以发现，所有满足 0\le j < i 且 s_i - s_j 第 bit 位为 1 的 j 都有贡献。而这样的 s_j 很有规律！它是一堆交替的区间组成的（这里的区间是值域意义上的），如下图：

因此，只需要在处理每一位时，都求出这样的交替区间的前缀和，查询时就能 O(1) 了。

具体来说，设 cnt_x 表示有多少个 s_i = x。在我们考虑第 i 位时，区间长度 t=2^i，f_v 表示 (v - 2t, v - t], (v - 4t, v - 3t], (v-6t,v-5t]\cdots 这些区间的 cnt 的和。

最后还有一点：我们需要去掉 0\le j < i 的限制，方法也很简单：把前缀桶换成全局桶，把有贡献的数对算两次，现在我们既要查询小于 s_i 的又要查询大于 s_i 的，维护一个前缀和，一个后缀和即可。这个地方可以看下面的暴力代码理解。

总复杂度 O((n+V)\log V)。

暴力代码（不加前缀和优化）：

    int n; cin >> n;
    vi a(n + 1), s(n + 1);
    F (i, 1, n) cin >> a[i];
    partial_sum(all(a), s.begin());
    F (i, 1, n) cnt[s[i]]++;
    int ans = 0;
    F (j, 0, 19) {
        int mx = s[n];
        int res = 0;
        F (i, 1, n)
        F (v, 0, mx) {
            if (abs(s[i] - v) & (1 << j)) {
                res += cnt[v];
            }
        }
        res /= 2;
        ans += (res & 1) << j;
    }
    F (i, 1, n) ans ^= s[i];
    cout << ans << '\n';

用前缀和优化后：

constexpr int maxn = 1e5 + 10, maxv = 1e6 + 10; 
int cnt[maxv], scnt[maxv];
int f[maxv], g[maxv];

#define val(p, t) ((t) >= 0 ? p[(t)] : 0)
#define val2(p, t) ((t) <= mx ? p[(t)] : p[mx])
#define val3(p, t) ((t) <= mx ? p[(t)] : 0)
// 处理边界

void OoO_main() {
    int n; cin >> n;
    vi a(n + 1), s(n + 1);

    F (i, 1, n) cin >> a[i];
    partial_sum(a.begin(), a.end(), s.begin());

    const int mx = s[n];

    F (i, 1, n) cnt[s[i]]++;
    partial_sum(cnt, cnt + mx + 1, scnt);

    int ans = 0;
    F (j, 0, 19) {
        int res = 0;
        fill(f, f + mx + 1); // 滚动数组节省空间
        F (i, 0, mx) {
            f[i] = val(f, i - (1 << (j + 1))) + val(scnt, i - (1 << j)) - val(scnt, i - (1 << (j + 1)));
        }
        DF (i, mx, 0) {
            g[i] = val3(g, i + (1 << (j + 1))) + val2(scnt, i + (1 << (j + 1)) - 1) - val2(scnt, i + (1 << j) - 1);
        }
        F (i, 1, n) {
            res += g[s[i]] + f[s[i]];
        }
        res /= 2;
        ans += (res & 1) << j;
    }

    F (i, 1, n) ans ^= s[i]; // 可能需要特殊处理一下区间和是 s[i] - s[0] 的情况
    cout << ans << '\n';
}

update on 2025.4.26：感谢管理员 Little_Cart 指出错误，并增加了一些补充说明。